Huge Numbers
Time limit40sMemory limit1024 MB
For each of T queries with positive integers A, N, P, compute A^(N!) mod P. N! is far too large to build, so the exponent must be reduced before the modular power is taken.
- Level
Medium7 of 10
- Topics
- Number theory, Math, Divide and conquer, Implementation
- Solved
- No attempts yet
Problem
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. Here N! denotes the product of the first N positive integers.
Input
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.
Output
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.
Limits
- 1 ≤ T ≤ 100.
Hint
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^6 = 729 is divided by 2, which is 1.