提示: 欢迎访问OurACM平台。
Problem 2050 Evil teacher's Final Problem

Accept: 10    Submit: 16
Time Limit: 15000 mSec    Memory Limit : 32768 KB

Problem Description

In the math class, the evil teacher gave you one unprecedented problem!

Here f(n) is the n-th fibonacci number (n >= 0)! Where f(0) = f(1) = 1 and for any n > 1, f(n) = f(n - 1) + f(n - 2). For example, f(2) = 2, f(3) = 3, f(4) = 5 ...

The teacher used to let you calculate f(n) mod p where n <= 10^18 and p <= 10^9, however , as an ACMER, you may just kill it in seconds! The evil teacher is mad about this. As you kill the Evil teacher.s problem in second too!!! now he let you calculate G(n,k) .Here G(n,0) = f(n) , G(n,i) = f( G(n,i-1) ) (k >= i >= 1). However the G(n,k) may be so large ,so you just need to output the remainder of the answer after divided by p.

Note: This problem is the evil teacher's final problem, it is really hard ! If you could solve this problem during the competition, you will be reward in the ACM_DIY gathering.

Input

The first line is one integer T indicates the number of the test cases. (T <=500000)

Then for every case, three integers n k and p . (0 <= n <= 10^9,0 <= k <= 10^4, 1 <= p <= 10^8)

Output

Output one line.

First output “Case #idx: ”, here idx is the case number count from 1.Then output remainder of the answer after divided by p.

Sample Input

10 1 10000 100000000 2 3 10000 3 97 98 4 2 10 5 1 29 1234 5678 100000000 3344 5566 77889900 10000 10000 100000000 1111 10000 90000000 999 876 10000000

Sample Output

Case #1: 1 Case #2: 2 Case #3: 3 Case #4: 4 Case #5: 5 Case #6: 17835789 Case #7: 5381861 Case #8: 71647609 Case #9: 43710337 Case #10: 9102595

Source

AekdyCoin

Submit  Back  Status  Discuss