LL modmul(LL A,LL B,LL mod)
{
return (A*B-(LL)((long double)A*B/mod)*mod+mod)%mod;
}
or
ll n,k,p;
ll kre(ll a,ll b){
a=a%p;
b=b%p;
return ((a*b-(ll)(((double)a*b+0.5)/p)*p)+p)%p;
}
ll kru(ll a,ll b){
ll ret=1;
while(b){
if(b&1){
ret=kre(ret,a)%p;
b--;
}
b/=2;
a=kre(a,a)%p;
}
return ret;
}