Modpow

long modpow(long base, long pw, long mod) {
    long ans = 1;
    base %= mod;
    while (pw > 0) {
        if (pw%2 == 1) ans = (ans*base)%mod;
        pw >>= 1;
        base = (base*base)%mod;
    }
    return ans;
}