1。
这其实是龟速乘

ll mul(ll a,ll b)
{
    ll ans=0;
    while(b)
    {
        if(b&1) ans=(ans+a)%mod;
        a=(a+a)%mod;
        b>>=1;
    }
    return ans;
}

2。
这个是O（1） 乘

ll mul(ll a,ll b,ll p)
{
    a%=p,b%=p;
    ll c=(long double)a*b/p;
    ll ans=a*b-c*p;
    if(ans<0) ans+=p;
    else if(ans>=p) ans-=p;
    return ans;
}