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