#include <iostream>
#include <queue>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <cstring>
#define inf 999999999
#define mo 1000000007
#define LL long long 
using namespace std;
const int N=4;
LL M;
LL fis[4]={1,0,1,0};
LL n,a,b,c,p;
struct mart
{
    LL num[4][4];
    mart(int x)
    {
        memset(num,0,sizeof(num));
        if (x==1) num[0][0]=c,num[0][1]=num[1][0]=num[2][0]=num[2][2]=1; 
        else if (x==2)
        {
            for (int i=0;i<4;i++)
                for (int j=0;j<4;j++)
                num[i][j]=(i==j);
        }
    }
    mart operator *(mart x)
    {
        mart y(0);
        for (int i=0;i<4;i++)
            for (int j=0;j<4;j++)
                for (int k=0;k<4;k++)
                y.num[i][j]=(y.num[i][j]+num[i][k]*x.num[k][j]%M)%M;
        return y;
    }
};
LL qow_mod(LL x,LL k,LL mod)
{
    LL res=1;
    while(k)
    {
        if(k&1) res=res*x%mod;
        x=x*x%mod,k>>=1;
    }
    return res;
}

LL pow(LL k)
{
    if (k==1) return 0;
    if (k==2) return 1;
    k-=2;
    mart a(1),res(2);
    while (k)
    {
        if (k&1) res=res*a;
        a=a*a,k>>=1;
    }
    LL ans=0;
    for(int i=0;i<N;i++)
        ans=(ans+fis[i]*res.num[i][0])%M;
    return ans;
}

int main()
{
    int t;
    scanf("%d",&t); 
    while (t--)
    {
        scanf("%I64d%I64d%I64d%I64d%I64d",&n,&a,&b,&c,&p);
        LL k=qow_mod(a,b,p);
        M=p-1;
        LL C=pow(n);
        printf("%I64d\n",qow_mod(k,C,p));
    }
     return 0;
}