\ \ \ \    Lcomyn 是个非常厉害的选手,除了喜欢写17kb+的代码题,偶尔还会写数学题.他找到了一个数列:

f_n=\left\{\begin{matrix} 1 ,&n=1 \\ a^b,&n=2 \\ a^bf_{n-1}^cf_{n-2},&otherwise \end{matrix}\right.f​n​​=​⎩​⎨​⎧​​​1,​a​b​​,​a​b​​f​n−1​c​​f​n−2​​,​​​n=1​n=2​otherwise​​

\ \ \ \    他给了你几个数:nn,aa,bb,cc,你须要告诉他f_nf​n​​模pp后的数值.

\ \ \ \    第一行一个数T,为測试数据组数.

\ \ \ \    每组数据一行,一行五个正整数,按顺序为nn,aa,bb,cc,pp.

\ \ \ \ 1\le T \le 10,1\le n\le 10^{18}    1≤T≤10,1≤n≤10​18​​,1\le a,b,c\le 10^91≤a,b,c≤10​9​​,p是质数且p\le 10^9+7p≤10​9​​+7.

\ \ \ \    对每组数据输出一行一个数,输出f_nf​n​​对pp取模后的数值.

1

5 3 3 3 233

190

发现f序列就是a的不同指数的形式。所以对每个f对a取对数。发现就是f[n]=b+c*f[n-1]+f[n-2]。

构造矩阵，高速幂搞。

注意由于是在指数上。所以模的值须要是欧拉函数p，由于p是质数。所以直接是p-1。

代码：

#pragma warning(disable:4996)

#include <iostream>

#include <functional>

#include <algorithm>

#include <cstring>

#include <vector>

#include <string>

#include <cstdio>

#include <cmath>

#include <queue>

#include <stack>

#include <deque>

#include <set>

#include <map>

using namespace std;

typedef long long ll;

#define INF 0x333f3f3f

#define repp(i, n, m) for (int i = n; i <= m; i++)

#define rep(i, n, m) for (int i = n; i < m; i++)

#define sa(n) scanf("%d", &(n))

const ll mod = 100000007;

const int maxn = 5e5 + 5;

const double PI = acos(-1.0);

ll n, a, b, c, p;

struct ma

{

	ll val[4][4];

	ma operator *(const ma &b)

	{

		int i, j, k;

		ma res;

		memset(res.val, 0, sizeof(res.val));

		for (k = 1; k <= 3; k++)

		{

			for (i = 1; i <= 3; i++)

			{

				for (j = 1; j <= 3; j++)

				{

					res.val[i][j] += (this->val[i][k] * b.val[k][j]) % (p - 1);

					res.val[i][j] %= (p - 1);

				}

			}

		}

		return res;

	}

};

ll po(ll x, ll y)

{

	ll res = 1;

	while (y)

	{

		if (y & 1)

			res = res*x%p;

		x = x*x%p;

		y >>= 1;

	}

	return res;

}

ma po_matrix(ma &x, ll y)

{

	ma res;

	res.val[1][1] = 1, res.val[1][2] = 0, res.val[1][3] = 0;

	res.val[2][1] = 0, res.val[2][2] = 1, res.val[2][3] = 0;

	res.val[3][1] = 0, res.val[3][2] = 0, res.val[3][3] = 1;

	while (y)

	{

		if (y & 1)

			res = res*x;

		x = x*x;

		y >>= 1;

	}

	return res;

}

void solve()

{

	ll i, j, k;

	scanf("%lld%lld%lld%lld%lld", &n, &a, &b, &c, &p);

	ll res;

	ma r;

	if (n == 1)

	{

		puts("1");

	}

	else if (n == 2)

	{

		res = po(a, b);

		printf("%lld\n", res);

	}

	else

	{

		r.val[1][1] = c, r.val[1][2] = 1, r.val[1][3] = b;

		r.val[2][1] = 1, r.val[2][2] = 0, r.val[2][3] = 0;

		r.val[3][1] = 0, r.val[3][2] = 0, r.val[3][3] = 1;

		r = po_matrix(r, n - 2);

		res = r.val[1][3] + r.val[1][1] * b;

		res = po(a, res);

		printf("%lld\n", res);

	}

}

int main()

{

#ifndef ONLINE_JUDGE

	freopen("i.txt", "r", stdin);

	freopen("o.txt", "w", stdout);

#endif

	int t;

	scanf("%d", &t);

	while (t--)

	{

		solve();

	}

	return 0;

}