SPOJ.com - Problem SEQAGAIN

SEQAGAIN - Easy Sequence!

no tags

Your task is to find the n^thterm of the following sequence :

F(n) = [F(n-1)*F(n-2)]^K for n>1

F(0), F(1), n and K will be provided as input. Modulus for all calculations is 1000000007. You should print the answer modulo 1000000007 i.e. F(n)%1000000007

Input

Input starts with a line containing an integer T ≤ 5000 which is the number of test cases in the file. Your program will be run on several input files.

Each test case consists of four space separated integers : F(0), F(1), n and K.

Output

T lines containing one integer each, corresponding to the answers for the T test cases.

Constraints

0 ≤ n ≤ 10¹⁸

0 ≤ K ≤ 10⁹

0 ≤ F(0), F(1) ≤ 10⁶

Example

Input:
1
1 1 2 1

Output:
1

Submit solution!

hide comments

< Previous 1 2 Next >

	darryl: 2014-06-05 03:04:03 The following problem is quite similar http://www.spoj.com/problems/BFALG/ You should check it out.
	Nipun Poddar: 2014-06-05 03:04:03 would u plz check my submission, id-8685934..& tell me why its giving WA
	npsabari: 2014-06-05 03:04:03 Remember n can 0 also, in which case you have to print the given number! This gave 5 WA!
	Mostafa 36a2: 2014-06-05 03:04:03 RE: thanks :D that mean the answer will be less than 1000000007 always Edit: I feel Bad that i can't solve it until now :( Last edit: 2012-11-23 16:48:40
	devu: 2014-06-05 03:04:03 @Himanshu Sachdeva:Thanks a lot for answering my query. Hint:"<spoiler removed>" is a trap in which one may fell. RE : Yeah right! People do think too much! :D Last edit: 2014-06-05 03:05:40
	devu: 2014-06-05 03:04:03 @Himanshu Sachdeva : Could you please check my submission id 7222941 and tell me y i am getting wa!! Dont Know What this problem is looking for. I ran the same code upto eof,got wrong answer at 0.45 else getting wrong answer at 0.36. RE : I suggest you to write a brute force program for yourself and see the difference between its output and the output this solution of yours produces. Try some small test cases. Last edit: 2012-06-28 13:42:14
	:D: 2014-06-05 03:04:03 http://en.wikipedia.org/wiki/Modular_arithmetic
	Mostafa 36a2: 2014-06-05 03:04:03 "Modulus for all calculations is 1000000007." is it important to understand? cause i didn't :P what is the meaning of it??
	[Rampage] Blue.Mary: 2014-06-05 03:04:03 It seems that discrete logarithm will lead to TLE. Edit: Never mind, I've found some constant optimization and got AC. Last edit: 2012-06-27 07:56:30
	Alex Anderson: 2014-06-05 03:04:03 Do you take 0^0 as 1 or as 0? Or are there no test cases like that? EDIT: Also, Francky, you were right about Python probably being too slow, because Java was. RE: 0^0 should be 1. There are such test cases. EDIT by Alex: Thanks for the time extension Last edit: 2012-06-28 03:17:53

Submit solution!

Added by:	zingoba
Date:	2012-06-26
Time limit:	1s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64