提示: 欢迎访问OurACM平台。
Problem 1905 Snail Alice II

Accept: 9    Submit: 38
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Snail Alice is a snail indulged in math. One day, when she was walking on the grass, suddenly an accident happened. Snail Alice fell into a bottomless hole, which was deep enough that she kept falling for a very long time. In the end, she caught the lateral wall of the hole and stop falling down. She named the place where she stopped “lucky place” immediately.

Snail Alice decided to climb up along the wall from the “lucky place”. The first day she climbed up q^0 (q is a positive constant integer) meters, but at night when she fell asleep, she fell down q^1 meters. She was shocked when she woke up, and she decided to make an extra effort. The second day she finally climbed up q^2 meters. To her surprise, she fell down faster because of the tiredness. She fell down q^3 meters at night. The longer she climbed up the longer she fell down. But finally, she still climbed out of the hole and slept on the ground.

Lying on the grass safe, she was curious about a question. How many meters was the “lucky place” down under the ground? She remembered that the sum of the times of her climbing up and falling down is n (of course, n is odd), so the distance between the ground and the “lucky place” must be :1-q+q^2-q^3+...+(-1)^(n-1)*q^n-1.

As a math professor, she wouldn’t stop. She came up with a good problem to test her students. Here is the problem:

A function f(n), n is a positive integer, and

Given q and n, please calculate the value of f(n).Please note that q and n could be huge.

Input

The first line contains only one integer T indicates the number of test case. (1 <= T <= 10000)

For each test case:

The first line contains three integers x1, y1, representing q. q=x1^y1.

The second line contains two integers: x2 and y2, representing n. n=x2^y2.

The third line contains a single integer P, meaning that what you really should output is the formula’s value mod P.

Note: 0 < x1,y1,y2,z2 <= 10^9, 0 < P <= 10^9

Output

For each test case, print “Case #idx:” first where “idx” is the case index counted from one. Then print an integer which equals to the formula’s value mod P.

Sample Input

2 1 1 1 1 1000000000 1 1 2 1 1000000000

Sample Output

Case #1: 1 Case #2: 0

Hint

Here are two examples about the “mod” operation:

-5 mod 3 = 1 (but not -2 !)

5 mod 2 = 1

Modified from 2010 National Programming Invitational Contest Host by ZSTU -Snail Alice

Source

FOJ有奖月赛-2010年05月

Submit  Back  Status  Discuss