求解:

幂塔函数:
$$
a^{a^{a^{a^{}…}}}
$$

或另一种幂塔函数:
$$
a^{b^{c^{d^{…}}}}
$$

$\phi(x)$是欧拉函数

欧拉降幂:
$$
a^{b} \equiv\left{\begin{array}{ll}a^{b % \phi(p)} & g c d(a, p)=1 \a^{b} & g c d(a, p) \neq 1, b<\phi(p) \a^{b % \phi(p)+\phi(p)} & g c d(a, p)\neq 1, b \geq \phi(p)\end{array} \quad(\bmod p)\right.
$$

code模板: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
using ll = long long;
using namespace std;

#define MOD(a,b) a>=b?a%b+b:a  //重定义取模，按照欧拉定理的条件
const int maxn = 1e6 + 10;

map<int, int> ma;
ll w[maxn], m, r, x;

ll qpow(ll a, ll b, ll mod) { //快速幂
    ll res = 1;
    while (b) {
        if (b & 1) res = MOD(res * a, mod);
        a = MOD(a * a, mod);
        b >>= 1;
    }
    return res;
}

ll getphi(ll x) {  //求互质个数
    ll ans = x;
    if (ma.count(x)) return ma[x];
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) {
            ans = ans / i * (i - 1);
            while (x % i == 0)
                x /= i;
        }
    }
    if (x > 1) ans = ans / x * (x - 1); //*****
    ma[x] = ans;
    return ans;
}
ll solve(int ceng, ll mod) { //每层的幂是w[i]
    if (ceng == r || mod == 1)
        return MOD(w[ceng], mod);
    return
        qpow(w[ceng], solve(ceng + 1, getphi(mod)), mod);
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        //scanf("%lld %lld %lld", &x, &r, &m);
        scanf("%lld %lld", &r, &m);
        if (!r) {
            cout << 1 % m << endl;
            continue;
        }
        //for (int i = 1; i <= r; i++) // 这个地方如果求幂塔函数(a^a^a^a^...)就这样写, 如果求a^b^c^d^...就自己输入w[i] 
            //w[i] = x;
        for (int i = 1; i <= r; i++)
            scanf("%lld", &w[i]);
        printf("%lld\n", solve(1, m) % m);
    }
    return 0;
}