거대한 수
시간 제한40초메모리 제한1024 MB
양의 정수 A, N, P가 주어질 때 A^(N!)을 P로 나눈 나머지를 각 테스트마다 구한다. N!은 직접 만들 수 없을 만큼 크므로 지수를 줄인 뒤 거듭제곱을 계산한다.
문제
셰쿠 교수는 오늘도 아키에게 문제를 하나 냈다. 양의 정수 A, N, P를 주고 A^(N!)을 P로 나눈 나머지를 구하게 했다. 여기서 N!은 처음 N개의 양의 정수를 모두 곱한 값이다.
입력
첫 줄에 테스트 케이스의 수 T가 주어진다. 이어서 T개의 줄이 주어지며, 각 줄에는 위에서 설명한 세 정수 A, N, P가 공백으로 구분되어 들어 있다.
출력
각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고 y는 답이다.
제한
- 1 ≤ T ≤ 100.
힌트
예제 1에서 답은 2^(1!) = 2를 2로 나눈 나머지이므로 0이다.
예제 2에서 답은 3^(3!) = 3^6 = 729를 2로 나눈 나머지이므로 1이다.