Power towers

You are given a non-empty list of positive integers $[x_1, x_2, \dots, x_N]$. The power tower of this list is the number

$x_1^{x_2^{\cdot^{\cdot^{\cdot^{x_N}}}}}$

The exponents are evaluated from the top down, so the value is $x_1^{\left(x_2^{\left(\cdots^{x_N}\right)}\right)}$.

A power tower grows very large even when the list holds only a few small integers. The power tower of $[2, 3, 2]$ is $2^{3^2} = 2^9 = 512$, and the power tower of $[5, 2, 3, 2]$ is $5^{512}$, which has 358 decimal digits.

Compute each power tower modulo a given positive integer $M$.

The first line contains two positive integers $T$ and $M$. Each of the next $T$ lines contains a positive integer $N$ followed by $N$ positive integers $x_1, x_2, \dots, x_N$. Consecutive numbers on a line are separated by exactly one space.

Print $T$ lines. Line $k$ contains the power tower of the $k$-th list modulo $M$.

• $1 \le T \le 1000$
• The lengths $N$ of all lists sum to at most $10^6$.
• $1 \le x_i \le 10^6$
• $1 \le M \le 10^9$

When $M = 10$, the answer for each list is the last decimal digit of its power tower. Most of the lists in the sample input have a power tower too large to fit in a 32-bit or 64-bit integer.