박테리아 증식 (Large)

시간마다 x마리가 x의 x제곱 마리로 늘어날 때 A마리에서 B시간 뒤 마릿수를 C로 나눈 나머지를 구합니다.

보통7정수론재귀수학아직 제출이 없습니다시간 제한5초메모리 제한512 MB

문제 설명

예제2

미생물을 연구하는 파스칼은 증식 방식이 특이한 박테리아를 발견했다. 어느 순간에 박테리아가 $x$ 마리 있으면, 이상적인 환경에서는 한 시간 뒤에 $x^x$ 마리가 된다.

이 성질을 더 깊이 조사하려고, 세 정수 $A$ , $B$ , $C$ 가 주어질 때 박테리아 $A$ 마리가 $B$ 시간 뒤에 몇 마리가 되는지 구하는 프로그램을 작성한다. 답이 매우 커지므로 그 값을 $C$ 로 나눈 나머지를 출력한다.

첫째 줄에 테스트 케이스의 개수 $T$ 가 주어진다. 이어지는 $T$ 개의 줄에 각 테스트 케이스가 한 줄씩 주어진다.

각 테스트 케이스는 공백으로 구분된 세 정수로 이루어지고, 순서대로 $A$ , $B$ , $C$ 이다.

각 테스트 케이스마다 다음 형식으로 한 줄씩 출력한다.

Case #X: N

$X$ 는 1부터 시작하는 테스트 케이스 번호이고, $N$ 은 박테리아의 수를 $C$ 로 나눈 나머지이다.