13970번 - Power towers 서브태스크다국어

Suppose that we have a non empty list of positive integers: [x₁, x₂, ..., x_N]. The power tower corresponding to this list is the number defined as:

$x_1^{x_2^{.^{.^{.^{x_n}}}}}$, that is $x_1^{\left(x_2^{\left(.^{.^{.^{x_n}}}\right)}\right)}$.

Power towers can be very big numbers, even when the list consists of only a few small integers. For example, the power tower of the list [2, 3, 2] is equal to 2⁹ = 512, and that of [5, 2, 3, 2] is equal to 5⁵¹² and has 358 decimal digits. In this task, you will have to compute power towers modulo a given positive integer M.

The first line of the input will contain two positive integers: T and M. Each of the following T lines will contain a positive integer N, followed by a list of N positive integers x₁, x₂, ... x_N. There will be exactly one space separating consecutive numbers in all lines of the input.

The output must contain T lines, each containing a single non-negative integer. The number in line k must be equal to the result of the power tower for the k-th given list modulo M.

In all subtasks, 1 ≤ T ≤ 1 000, the sum of the lengths N of all lists will not exceed 1 000 000, and 1 ≤ x_i ≤ 1 000 000.

In this example, as M = 10, we are interested in the last decimal digit of each power tower. Notice that, except for the first three power towers and the last one, all the others are too large to be represented with 32 or 64 bit integers.