24009번 - Huge Numbers 서브태스크다국어

문제

Professor Shekhu has another problem for Akki today. He has given him three positive integers A, N and P and wants him to calculate the remainder when A^N! is divided by P. As usual, N! denotes the product of the first N positive integers.

입력

The first line of the input gives the number of test cases, T. T lines follow. Each line contains three integers A, N and P, as described above.

출력

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the answer.

제한

• 1 ≤ T ≤ 100.

Test Set 1 (9점)

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

Test Set 2 (14점)

• 1 ≤ A ≤ 10⁵.
• 1 ≤ N ≤ 10⁵.
• 1 ≤ P ≤ 10⁵.

힌트

In Sample Case #1, the answer is the remainder when 2^1! = 2 is divided by 2, which is 0.

In Sample Case #2, the answer is the remainder when 3^3! = 3⁶ = 729 is divided by 2, which is 1.