16432 | 거대한 수

Shekhu 교수는 오늘 Akki에게 또 다른 문제를 냈다. 그는 Akki에게 세 양의 정수 A, N, P를 주고 $A^{N!}$ 을 P로 나눈 나머지를 계산하게 한다. 평소와 같이 N!은 처음 N개의 양의 정수의 곱을 나타낸다.

1 ≤ T ≤ 100. 시간 제한: 테스트 세트당 40초. 메모리 제한: 1GB.

1 ≤ A ≤ 10. 1 ≤ N ≤ 10. 1 ≤ P ≤ 10.

1 ≤ A ≤ $10^{5}$ . 1 ≤ N ≤ $10^{5}$ . 1 ≤ P ≤ $10^{5}$ .

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 줄이 주어진다. 각 줄에는 위에서 설명한 세 정수 A, N, P가 들어 있다.

각 테스트 케이스마다 Case #x: y을 담은 한 줄을 출력한다. 여기서 x은 테스트 케이스 번호이며(1부터 시작), y은 정답이다.

2
2 1 2
3 3 2

Case #1: 0
Case #2: 1

예제 케이스 #1에서 정답은 2^{1!} = 2을 2로 나눈 나머지인 0이다.

예제 케이스 #2에서 정답은 3^{3!} = $3^{6}$ = 729을 2로 나눈 나머지인 1이다.