OnlineJudge 3 现已推出。点此体验新版：A^X MOD P | SDUT OnlineJudge
A^X MOD P
Time Limit: 1000 ms
Memory Limit: 65536 KiB
Problem Description
Given f(x), for the following definition.
f(x) = K, x = 1
f(x) = (a*f(x-1) + b)%m , x > 1
Now, Your task is to calculate
( A^(f(1)) + A^(f(2)) + A^(f(3)) + ...... + A^(f(n)) ) modular P.
Input
The first line contains a number T, for the test cases(T < 40).
And,
1 <= n <= 10^6
0 <= A, K, a, b <= 10^9
1 <= m, P <= 10^9
Output
Please out put the answer in the format of the following, “Case #c: ans”. c is the number start from 1.
Sample Input
1 3 15 123 2 3 1000 107
Sample Output
Case #1: 63
Hint
Source
zhengnanlee