快速乘

ll multi(ll x,ll y){
  ll ans = (x * y - (ll)((long double)x / mod * y + 1.0e-8) * mod);
  return ans < 0 ? ans + mod : ans;
}

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