거듭제곱 탑

비어 있지 않은 양의 정수 목록 $[x_1, x_2, \dots, x_N]$이 주어진다. 이 목록에 대응하는 거듭제곱 탑은 다음 수이다.

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

지수는 위쪽부터 차례로 계산한다. 즉 $x_1^{\left(x_2^{\left(\cdots^{x_N}\right)}\right)}$이다.

거듭제곱 탑은 목록이 작은 정수 몇 개로만 이루어져 있어도 매우 큰 수가 된다. 목록 $[2, 3, 2]$의 거듭제곱 탑은 $2^{3^2} = 2^9 = 512$이고, 목록 $[5, 2, 3, 2]$의 거듭제곱 탑은 $5^{512}$로 십진수 358자리이다.

거듭제곱 탑을 주어진 양의 정수 $M$으로 나눈 나머지를 구하는 프로그램을 작성하시오.

첫째 줄에 양의 정수 $T$와 $M$이 주어진다. 이어지는 $T$개의 줄에는 각각 양의 정수 $N$과 그 뒤로 $N$개의 양의 정수 $x_1, x_2, \dots, x_N$이 주어진다. 한 줄에서 이웃한 두 수 사이에는 공백이 정확히 하나 있다.

$T$개의 줄을 출력한다. $k$번째 줄에는 $k$번째 목록의 거듭제곱 탑을 $M$으로 나눈 나머지를 출력한다.

• $1 \le T \le 1000$
• 모든 목록의 길이 $N$을 더한 값은 $10^6$ 이하이다.
• $1 \le x_i \le 10^6$
• $1 \le M \le 10^9$

$M = 10$이면 각 거듭제곱 탑의 마지막 자리 숫자를 구하는 셈이다. 예제 입력에 있는 목록은 대부분 거듭제곱 탑이 32비트나 64비트 정수에 담기지 않을 만큼 크다.