SPOJ.com - Problem POWPOW2

POWPOW2 - Power with Combinatorics(HARD)

no tags

Your task is to calculate a^(b^(exp)).

a: provided in input, 10^5 >= a >= 0
b: provided in input, 10^5 >= b >= 0
exp = (nC0)^2 + (nC1)^2 + (nC2)^2 + ... +(nCn)^2
n: provided in input, 10^5 >= n >= 0

Note: The Output for 0^0 should be 1.

nCr denotes n choose r.

As the answer can be too large, you need to output modulo 10^9+7.

Input

The first line of each input file contains number of test cases t (t<=1000).

Then follow a new line.

Then follow t lines, each containing 3 integers, (i.e. a b n in order) each of them separated by a space.

Output

Output contains t lines, ith line contains the answer of the ith test case.

Example

Input:
1

1 1 1

Output:
1

Explanation

In First test case, the Value of exp is 2, value of 1^(1^2) is 1, so output is 1.

Note: First try out the tutorial version where limits are low. POWRTU

Click here to see my set of problems at SPOJ.

Submit solution!

hide comments

< Previous 1 2 3 4 Next >

	Sameer Jain: 2013-09-04 04:43:08 1 458 9575 7458 What is the answer for this test case
	Francky: 2013-09-04 04:43:08 @pushap : verify again your 0 0 cases with 3 9 0 0 0 0 9 0 0 0
	pushap: 2013-09-04 04:43:08 getting WA still!!tested every case of 0^0 and passed tutorial problem. please give me a test case......
	Out0fbounds: 2013-09-04 04:43:08 @ tjandra i have same problem getting corrct answer for 1 79981 79981 79981 can u help finding tricky case of this problem.. plzz Re:I wuld advice u to first check ur code for smaller values in the easier mode of the problem. Its not at all tricky,the only trick lies in 0^0 case,just ponder over it. Last edit: 2012-08-12 14:37:55
	Code for food: 2013-09-04 04:43:08 Very tricky indeed :-) Re:Thnxs for ur appreciation :) Last edit: 2012-08-12 14:38:41
	(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2013-09-04 04:43:08 Finally got AC, best "tricky" problem I ever met on SPOJ. Thanks a lot to my friend Jona Martinus Manullang for helping me finding "tricky" test cases :-) @Tjandra : Thanks for your appreciation :) Last edit: 2012-07-31 12:18:04
	Francky: 2013-09-04 04:43:08 @ Mario : Try all cases with 0 0: 3 9 0 0 0 0 9 0 0 0 ;-) There's such case that aren't in EASY.
	MarioYC: 2013-09-04 04:43:08 What kind of test is #8? I seem to be failing at that one. I tried lots of random test cases but none seem to fail :( Re:No Special Test Cases,check for the base case i.e 0^0 Edit:That case seems to be working, that should be covered in the tutorial version right? I got AC in that one Re:Tutorial Version dint contain any tricky test cases like 0^0 ,it just contained small values of a,b,n Re:Congrats :) Last edit: 2012-07-26 20:54:19
	15972125841321: 2013-09-04 04:43:08 Finally got it!!! Amazing problem.... had to take care of other things besides calculating "exp". Last edit: 2012-07-21 16:18:46
	Niklas Baumstark: 2013-09-04 04:43:08 Great problem! It's nice that the time limit isn't too strict, as implementing the raw algorithm was challenging enough at least for me :) Re:Thnxs for ur appreciation :) Last edit: 2012-07-20 04:46:43

Submit solution!

Added by:	devu
Date:	2012-07-14
Time limit:	0.100s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64
Resource:	Utkarsh Lath