{
	ll@s;
	rep(s){
		ll@n;Mint@m;ll@x;
		Mint a=(1+m)**n;
		Mint b=(1-m)**n;
		wt(x?(a-b)/2:(a+b)/2);
	}
}