//a^b mod m
long long modpow(long long a, long long b, long long m) {
    long long ret = 1;
    long long mul = a;
    for ( ; b > 0; b = b >> 1) {
        if ( b&1 ) {
            ret = (ret * mul) % m;
        }
        mul = (mul * mul) % m;
    }
    return ret;
}