【黑科技整理】O1 快速乘

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;
}