#include<bits/stdc++.h>
using namespace std;
inline int qread()
{
    int a=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){(a*=10)+=(ch^48);ch=getchar();}
    return a*f;
}
int T,n,m,k,x,p,w,que[10010],ed,ans;
inline int qpow(long long x,int y,int mod)
{
    long long cx=1;
    while(y)
    {
        (y&1)&&((cx*=x)%=mod);
        (x*=x)%=mod;
        y>>=1;
    }
    return cx;
}
inline int get_yg(int p)
{
    ed=0;
    int P=p-1;
    for(int i=2;i*i<=P;++i)
    {
        if(P%i==0)que[++ed]=i;
        while(P%i==0)P/=i;
    }
    if(P!=1)que[++ed]=P;
    for(int i=2,op;;++i)
    {
        op=1;
        for(int j=1;j<=ed;++j)
        {
            if(qpow(i,p/que[j],p)==1)
            {
                op=0;
                break;
            }
        }
        if(op)return i;
    }
}
int main()
{
    T=qread();
    while(T--)
    {
        n=qread();x=qread()%n;k=qread();
        m=qread()%n;p=qread();w=get_yg(p);
        ans=0;
        x-=m;while(x<0)x+=n;
        w=qpow(w,(p-1)/n,p);
		for(int i=0,W=1;i<n;++i,W=1ll*W*w%p)ans=(1ll*ans+1ll*qpow(W,n-x,p)*qpow(1+W,k,p))%p;
        printf("%lld\n",1ll*ans*qpow(n,p-2,p)%p);
    }
    return 0;
}