快速幂&快速乘

LL mult_mod(LL a, LL b, LL c)
{
    a %= c; b %= c;
    LL ret = 0;
    LL tmp = a;
    while (b){
        if (b & 1){
            ret += tmp; 
            if (ret > c) ret -= c;//直接取模慢很多
        }
        tmp <<= 1;
        if (tmp > c) tmp -= c;
        b >>= 1;
    }
    return ret;
}

LL pow_mod(LL a, LL n, LL mod)
{
    LL ret = 1;
    LL temp = a%mod;
    while (n){
        if (n & 1) ret = mult_mod(ret, temp, mod);
        temp = mult_mod(temp, temp, mod);
        n >> 1;
    }
    return ret;
}