거듭제곱 탑

비어 있지 않은 양의 정수 목록 $[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$ 으로 나눈 나머지를 출력한다.

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