int calc(int a,int b,int c)
{
int ret=1;
a%=c;
while (true)
{
if (b&1) ret=(ret*a)%c;
if (b>>=1) a=(a*a)%c;
else break;
}
return ret;
}