快速乘
ll qmul(ll a, ll b){
ll sum = 0;
while(b){
if(b & 1) sum = sum + a;
while(sum >= mod) sum -= mod;
a = a + a;
while(a >= mod) a -= mod;
b >>= 1;
}
return sum;
}
ACM模板库
ll qmul(ll a, ll b){
ll sum = 0;
while(b){
if(b & 1) sum = sum + a;
while(sum >= mod) sum -= mod;
a = a + a;
while(a >= mod) a -= mod;
b >>= 1;
}
return sum;
}