template<class T,class T1> T fast_mod(T a,T b,T1 Mod){
a%=Mod;
if(b==0) return 1;
T ans=1,base=a;
while(b!=0){
if(b&1)ans=(ans*base)%Mod;
base=(base*base)%Mod;
b>>=1;
}
return ans;
}