快速幂
求a^b(%mod)
ll pow(ll a,ll b,ll c)
{
ll ans=1,bas=a;
while(b)
{
if(b&1) ans=(ans*bas)%c;
bas=(bas*bas)%mod;
b>>=1;
}
return ans;
}
如果是接近1e18的数字的快速幂，则会爆long long，这就要用快速乘;
ll multi(ll a,ll b,ll c)
{
ll ans=0;
while(b)
{
if(b&1)
ans=(ans+a)%c;
a=(a+a)%c;
b>>=1;
}
return ans;
}
ll pow(ll a,ll b,ll c)
{
ll ans=1,bas=a;
while(b)
{
if(b&1)
ans=multi(ans,bas,c);
bas=multi(bas,bas,c);
b>>=1;
}
return ans;
}