#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;
#define getmid(l,r) ((l) + ((r) - (l)) / 2)
#define MEM(a,b) memset(a,b,sizeof(a))
#define MP(a,b) make_pair(a,b)
#define PB push_back
#define X first
#define Y second

const double eps = 1e-8;
const double pi = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int MAXN = 100010;

int T;
ll n;
ll a,b,c,p;

struct Mx{
    ll a[3][3];
    void clear(){ memset(a,0,sizeof(a)); }
    void stand(){ clear(); for(int i = 0; i < 3; ++i) a[i][i] = 1; }
    Mx operator * (const Mx &b){
        Mx c; c.clear();
        for(int k = 0; k < 3; ++k){
            for(int i = 0; i < 3; ++i){
                for(int j = 0; j < 3; ++j){
                    c.a[i][j] = (c.a[i][j] + a[i][k] * b.a[k][j]);
                    if(c.a[i][j] >= (p - 1)){
                        c.a[i][j] = (c.a[i][j] % (p - 1) + p - 1);
                    }
                }
            }
        }
        return c;
    }
};

Mx Solve(ll m){
    Mx res; res.stand();
    Mx t; t.clear();
    t.a[0][0] = 1; t.a[0][1] = c; t.a[0][2] = 1;
    t.a[1][0] = c; t.a[1][1] = (c * c + 1); t.a[1][2] = (c + 1);
    t.a[2][0] = 0; t.a[2][1] = 0; t.a[2][2] = 1;

    if(t.a[1][1] >= p - 1){
        t.a[1][1] = (t.a[1][1] % (p - 1) + p - 1);
    }

    while(m){
        if(m & 1) res = res * t;
        t = t * t;
        m >>= 1;
    }
    return res;
}

ll Q_pow(ll x,ll y){
    ll res = 1;
    while(y){
        if(y & 1) res = res * x % p;
        x = x * x % p;
        y >>= 1;
    }
    return res % p;
}

int main(){
    ios::sync_with_stdio(false);
    cin >> T;
    while(T--){
        cin >> n >> a >> b >> c >> p;
        Mx ans; ans.clear();
        ans.a[0][0] = 0;
        ans.a[1][0] = b;
        ans.a[2][0] = b;
        ans = Solve((n - 1) / 2LL) * ans;
        ll v;
        if(n % 2) v = ans.a[0][0];
        else v = ans.a[1][0];
        //cout << "v : " << v << endl;
        ll res = Q_pow(a,v);
        cout << res << endl;
    }
    return 0;
}