long long Mul(long long tmp,long long res,long long mod){
long long ret=0;
while(res){
if(res&1) ret=(ret+tmp)%mod;
if(tmp>MAXN)tmp=tmp-(mod-tmp);
else tmp=(tmp<<1)%mod;
res>>=1;
}
return ret;
}
//或者O(1)
LL mul(LL a,LL b,LL c){ return ((a*b-(LL)((long double)a/c*b+1e-8)*c)%c+c)%c; }
