BFALG - Brute-force Algorithm EXTREME

Please click here to download a PDF version of the contest problems. The problem is problem B in the PDF. But the data limits is slightly modified: 1≤P≤1000000 in the original description, but in this EXTREME version, 1≤P≤1000000000.

=========(EDIT, Francky)===============

Professor Brute is not good at algorithm design. Once he was asked to solve a path finding problem. He worked on it for several days and finally came up with the following algorithm:

Function Find(integer n, function func)
	If n=1
		For i = 1 to a do func()
	Elseif n=2
		For i = 1 to b do func()
	Else Find(n-1,Find(n-2,func))

Function Main
	Find(n, funny)

Any fool but Brute knows that the function “funny” will be called too many times. Brute wants to investigate the number of times the function will be called, but he is too lazy to do it.

Now your task is to calculate how many times the function “funny” will be called, for the given a, b and n. Because the answer may be too large, you should output the answer module by P.

Input

There are multiple test cases. The first line of the input contains an integer T, meaning the number of the test cases.

For each test cases, there are four integers a, b, P and n in a single line. You can assume that 1≤n≤1000000000, 1≤P≤1000000, 0≤a, b<1000000.

Output

For each test case, output the answer with case number in a single line.

Example

Input:
3
3 4 10 3
4 5 13 5
3 2 19 100

Output:
Case #1: 2
Case #2: 11
Case #3: 12

Added by:Fudan University Problem Setters
Date:2009-11-01
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 C99 GOSU NODEJS OBJC PERL6 VB.NET
Resource:ACM/ICPC Regional Contest, Shanghai 2009

hide comments
2023-11-12 14:36:35
Why can't I see my wrong infomations in Spoj :(
2017-08-29 18:46:55 mike
be aware of double datatype as it would give significant error in calculation. Avoid it ;)
2014-05-03 19:32:59 Francky
I've edit the body to include the description. This problem is cool and a must have solved. Hope problem setters will appreciate. ;-)

Last edit: 2016-03-25 02:06:05
2013-07-18 20:11:58 Dhaval Joshi
cannot find the problem link .
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.