long long powMod(long long n, long long pow, long long mod)
{
    long long res=1;
    do {
        if(pow&1)
            res=(res*n)%mod;
        n=(n*n)%mod;
    } while(pow>>=1);
    return res;
}