#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <map>
#include <stack>
#include <vector>
#include <memory.h>
#include <set>
#include <string.h>
#include <list>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <queue>
#include <time.h>
#define ll long long
#define forn(i,n) for(int i=0;i<n;++i)
#define rep(i,n) for(int i=1;i<=n;++i)
#define repc(i,l,r) for(int i=l;i<=r;++i)
#define mp(a,b) make_pair(a,b)
#define llf long double
#define pii pair<int,int>
using namespace std;
ll mod;
struct Node{
    ll a[3][3];
    Node operator *(Node x){
        Node res = {};
        forn(i, 3)forn(j, 3){
            ll t = 0;
            forn(k, 3){
                t = (t + a[i][k] * x.a[k][j]) % (mod-1);
            }
            res.a[i][j] = t;
        }
        return res;
    }
};
Node pow(Node x,ll n){
    Node res;
    memset(&res, 0, sizeof(res));
    res.a[0][0] = res.a[1][1] = res.a[2][2] = 1;
    while (n){
        if (n & 1){
            res = res*x;
        }
        x = x*x;
        n >>= 1;
    }
    return res;
}
ll pow(ll x, ll n){
    ll res = 1;
    while (n){
        if (n & 1)res = res*x%mod;
        x = x*x%mod;
        n >>= 1;
    }
    return res;
}
void solve(){
    ll n,a, b, c;
    cin >> n >> a >> b >> c >> mod;
    Node t;
    memset(&t, 0, sizeof(t));
    t.a[0][0] = 1;
    t.a[0][2] = 1;
    t.a[1][2] = 1;
    t.a[2][1] = 1;
    t.a[2][2] = c;
    t = pow(t, n - 1);
    ll x = pow(a, b);
    ll res = pow(x, t.a[0][1]+t.a[2][1]);
    cout << res << endl;

}
int main(){
    //freopen("abc.txt", "r", stdin);
    int T;
    cin >> T;
    while (T--){
        solve();
    }
    return 0;
}