快速幂模板

ll modpow(ll a, ll b)
{
    ll ans = 1, base = a%MOD;
    while(b != 0)
    {
        if(b&1 != 0)
            ans = (ans*base)%MOD; 
        base = (base*base)%MOD;
        b >>= 1;
    }
    return ans%MOD;
}