inline LL Mul_Mod(LL a, LL b , LL Mod)
{
	LL ans = 0 ;
	b %= Mod ;
	while (b) {
		if (b&1) ans = (ans + a ) % Mod ;
		b = b >> 1 ;
		a = a << 1 ;
		a %= Mod ;
	}
	return ans ;
}
inline LL Quick_Mod(LL a,int k,LL Mod)
{
	LL ans = 1 ;
	a %= Mod ;
	while (k) {
		if (k&1) ans = Mul_Mod(ans,a,Mod) ;
		k = k >> 1 ;
		a = Mul_Mod(a,a,Mod) ;
	}
	return ans ;
}