C++ 快速幂和大数乘法（取模）

int qpow(int a, int b) {
    int ans = 1, base = a;
    while (b != 0) {
        if (b & 1) ans *= base;
        base *= base;
        b >>= 1;
    }
    return ans;
}

long long qmul(long long a, long long b, long long mod) {
    long long res = 0;
    while (b) {
        if (b & 1) res = (res + a) % mod;
        (a <<= 1) %= mod;
        b >>= 1;
    }
    return res;
}

long long qpow_mod(long long a, long long n, long long mod) {
    long long ret = 1;
    while (n) {
        if (n & 1) ret = qmul(ret, a, mod);
        a = qmul(a, a, mod);
        n >>= 1;
    }
    return ret;
}