# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
struct Fastmod
{
	int m;ull b;
	void init(int _m){m=_m;b=((lll)1<<64)/m;}
	int operator()(ll a)const
	{
		ll q=((lll)a*b)>>64;a-=q*m;
		return a>=m?a-m:a;
	}
}Mod;
int mod;
int add(int a,int b){return (a+=b)>=mod?a-mod:a;}
int mul(int a,int b){return Mod((ll)a*b);}
int power(int a,int b)
{
	int ans=1;
	for(;b;b>>=1,a=mul(a,a))
		if(b&1) ans=mul(ans,a);
	return ans;
}
int getG(int P)
{
	int phi=P-1,t=phi;
	vector<int> pr;
	for(int i=2;i*i<=t;i++)
		if(t%i==0)
		{
			pr.push_back(i);
			for(;t%i==0;t/=i);
		}
	if(t>1) pr.push_back(t);
	for(int g=1;;g++)
	{
		bool ok=1;
		for(int p:pr)
			if(power(g,phi/p)==1)
			{
				ok=0;
				break;
			}
		if(ok) return g;
	}
}
int main()
{
	int T,n,m,k,p;
	cin>>T;
	while(T--)
	{
		scanf("%d%d%d%d%d",&n,&m,&k,&p,&mod);Mod.init(mod);
		int g=getG(mod),wm=power(g,(mod-1)/n),x=power(wm,(p-m+n)%n),ans=0;
		for(int i=0,w=1,pw=1;i<n;w=mul(w,wm),pw=mul(pw,x),i++) ans=Mod(ans+(ll)power(w+1,k)*pw);
		printf("%d\n",mul(power(n,mod-2),ans));
	}
	return 0;
}