#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<list>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#define mem(x,y) memset(x,y,sizeof(x))
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pii;
#define bug puts("===========");
const double pi=(acos(-1.0));
const double eps=1e-8;
const ll INF=1e18+10;
const ll inf=1e14;
const int maxn=1000+10;
//const int mod=100000007;
/*===============================*/

const int Mn = 101;
const int Mm = 101;
typedef long long mytype;
ll Mmod=1e9+7;
struct Matrix {
    int n, m;
    mytype a[Mn][Mm];
    void init() {
        memset(a, 0, sizeof(a));
    }
    Matrix(int n=Mn,int m=Mm):n(n),m(m) {}
    void U(int Size)//将现有矩阵转换为一个同等大小的单位矩阵
    {
        n=m=Size;
        init();
        for (int i = 0; i < n; i++)
        a[i][i] = 1;
    }
    Matrix unit() {//构造一个同等大小的单位矩阵
        Matrix tmp(n,n);
        tmp.init();
        for (int i = 0; i < n; i++)
        tmp.a[i][i] = 1;
        return tmp;
    }
    Matrix operator + (const Matrix &b) const {
        Matrix tmp(n,m);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                tmp.a[i][j] = a[i][j] + b.a[i][j];
        return tmp;
    }
    Matrix operator - (const Matrix &b) const {
        Matrix tmp;
        tmp.n = n, tmp.m = m;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) tmp.a[i][j] = a[i][j] - b.a[i][j];
        return tmp;
    }
    Matrix operator * (const Matrix &b) const {
        Matrix tmp(n,b.m);
        tmp.init();
        for (int i = 0; i < n; i++)
             for (int j = 0; j < m; j++) {
            if (!a[i][j]) continue;
            for (int k = 0; k < b.m; k++)
            tmp.a[i][k] += a[i][j] * b.a[j][k]%Mmod, tmp.a[i][k] %= Mmod;
        }
        return tmp;
    }
    Matrix operator * (const mytype &b) {
        Matrix tmp(n,m);
        for (int i = 0; i < n; i++)
             for (int j = 0; j < m; j++) {
            tmp.a[i][j] = a[i][j] * b;//% mod;
        }
        return tmp;
    }
    Matrix operator !() {//矩阵转置
        Matrix tmp(m,n);
        for (int i = 0; i < m; i++)
             for (int j = 0; j < n; j++)
            tmp.a[j][i] = a[i][j];
        return tmp;
    }
    friend Matrix pow(Matrix a, mytype b) {//矩阵快速幂
        if(b<0) return a.unit();
       Matrix tmp=a.unit();
        for (; b; b>>=1,a=a*a){
            if(b&1) tmp=tmp*a;
        }
            return tmp;
    }
    void IN(){
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
            scanf("%lld",&a[i][j]);
    }
    void OT(){
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            printf("%lld%c",a[i][j]," \n"[j==m-1]);
    }
};
ll euler(ll x) {
    ll res = x;
    for (ll i = 2; i <= x / i; i++) if (x % i == 0) {
        res = res / i * (i - 1);
        while(x % i == 0) x /= i;
    }
    if (x > 1) res = res / x * (x - 1);
    return res;
}
ll powmod(ll a,ll b,ll mod){
    ll ans=1;
    while(b){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
Matrix A,B;
int main()
{
    int T_T;
    ll n,a,b,c,p;
    scanf("%d",&T_T);
    while(T_T--){
        scanf("%I64d%I64d%I64d%I64d%I64d",&n,&a,&b,&c,&p);
        A.init();
        Mmod=euler(p);
        A.n=1; A.m=3;
        A.a[0][0]=0; A.a[0][1]=b; A.a[0][2]=b;
        B.n = B.m=3;
        B.a[0][0]=0; B.a[0][1]=1; B.a[0][2]=0;
        B.a[1][0]=1; B.a[1][1]=c; B.a[1][2]=0;
        B.a[2][0]=0; B.a[2][1]=1; B.a[2][2]=1;
        A=A*pow(B,n-1);
        ll z=A.a[0][0]+Mmod;
        ll ans=powmod(a,z,p);
        printf("%I64d\n",ans);
    }
    return 0;
}