#include <bits/stdc++.h>
using namespace std;
int Qread()
{
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    return x;
}
int qpow(int a,int p,int Mod)
{
    int ret=1;
    for(;p;p>>=1,a=1ll*a*a%Mod)
        if(p&1) ret=1ll*ret*a%Mod;
    return ret;
}
vector<int> yz;
int get_yg(int p)
{
    int rem=p-1;
    yz.clear();
    for(int i=2;i*i<=rem;i++)
        if(rem%i==0)
        {
            yz.push_back(i);
            while(rem%i==0) rem/=i;
        }
    if(rem!=1) yz.push_back(rem);
    int g=2;
    bool abl;
    for(;g<p;g++)
    {
        abl=true;
        for(int &t:yz)
            if(qpow(g,(p-1)/t,p)==1)
                abl=false;
        if(abl) return g;
    }
    return -1;
}
int n,m,k,x,p,g,w;
int ans;
long long tk;
void solve()
{
    n=Qread(),x=Qread(),k=Qread(),m=Qread(),p=Qread();
    g=get_yg(p);
    x=(n+x-m%n)%n;
    w=qpow(g,(p-1)/n,p);
    tk=0;
    for(int i=1,t=1;i<=n;i++,t=1ll*t*w%p)
        tk+=1ll*qpow(t,n-x,p)*qpow((t+1)%p,k,p)%p;
    ans=tk%p*qpow(n,p-2,p)%p;
    printf("%d\n",ans);
}
int main()
{
    int Q=Qread();
    while(Q--) solve();
    return 0;
}