//a 的 b 次方模 c
long mod(long a,long b,long c)
{
long stack[1000],cnt=-1,res;
for(;b!=1;b>>=1)
{
cnt++;
if(b%2==0) stack[cnt]=0;
else stack[cnt]=1;
}
res=a*a%c;
for(;cnt>0;cnt--)
{
if(stack[cnt]) res=(cnt*a%c)*(cnt*a%c)%c;
else res=res*res%c;
}
if(stack[0]) res=(res*a%c);
return res;
}