/*
快速幂、快速乘
*/
typedef long long ll;
ll qpow(ll num,ll p,ll mod){
ll res=1;
while(p){
if(p&1){
res=qmul(res,num,mod)%mod;
}
num=qmul(num,num,mod)%mod;
p>>=1;
}
return res%mod;
}
ll qmul(ll x,ll y,ll mod){
ll res=0;
while(y){
if(y&1){
res=(res+x)%mod;
}
x=(x+x)%mod;
y>>=1;
}
return res%mod;
}
