快速幂

• 常规快速幂

ll qpow(ll a,ll b,ll MOD){
    ll res=1%MOD;
    for(;b;b>>=1,a=a*a%MOD){
        if(b&1)res=res*a%MOD
    }
    return res;
}

• 长整型 with 防爆乘法

using ll = long long;
 
ll mul(ll a, ll b, ll m) { 
    a %= m, b %= m; 
    ll r = a * b - m * (long double)(1.L / m * a * b);
    return r - m * (r >= m) + m * (r < 0);
}
 
ll mul(ll a, ll b, ll m) {
    return (__int128)a * b % m;
}
 
ll qpow(ll a, ll b, ll m) {
    ll res = 1 % m; 
    for (; b; b >>= 1, a = mul(a, a, m)) {
        if (b & 1) res = mul(res, a, m);
    }
    return res;
}