快速幂

LL Q_pow(LL x,LL n,LL MOD) { LL res=1; while(n>0) { if(n&1) res=res*x%MOD;//二进制最低位为1，则乘上x^(2^i) x=x*x%MOD; n>>=1; } return res; }