문제 126

거듭제곱 탑의 나머지

태그 보기

구현

길이가 $N$인 음이 아닌 정수 배열 $A_1,A_2,\cdots,A_N$과 양의 정수 $M$이 주어진다. 다음 거듭제곱 탑을 $M$으로 나눈 나머지를 구해 보자.

\[ A_1^{\left(A_2^{\left(\cdots^{A_N}\right)}\right)}. \]

거듭제곱은 오른쪽부터 계산하며, $0^0=1$로 정의한다.

입력

첫 번째 줄에 테스트 케이스의 수를 의미하는 정수 $T$가 주어진다. $(1 \le T \le 1\,000)$ 각 테스트 케이스는 다음과 같이 주어진다.

첫 번째 줄에 두 정수 $N$, $M$이 공백으로 구분되어 주어진다. $(1 \le N \le 200\,000; 1 \le M \le 10^9)$

두 번째 줄에 배열의 원소 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(0 \le A_i \le 2^{63}-1)$

모든 테스트 케이스에 대한 $N$의 합은 $200\,000$ 이하이다.

각 테스트 케이스에서 구한 나머지를 테스트 케이스가 주어진 순서대로 한 줄에 하나씩 출력한다.

6
1 1
0
2 8
0 0
3 8
0 0 0
2 8
2 3
3 100
2 3 2
1 1000000000
9223372036854775807

언어