POWPOW - Power with Combinatorics

no tags 

Your task is to find a^(exp^(b)),

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 the input, 10^5 => n >= 0

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

nCr denotes n choose r.

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^(2^1) is 1, so output is 1.

Click here to see my set of problems at Spoj.


hide comments
kancha: 2013-12-20 18:16:33

testcase 8 is killing me now :(
feww....accepted al last!!
thanks for this problem :D

Last edit: 2013-12-20 19:09:07
Amitayush Thakur: 2013-11-02 15:28:14

Got AC after 18 attempts!!!
was getting WA for 8th test case repeatedly.
Was doing a very silly mistake :D :D

Himanshu: 2013-09-14 12:46:01

repeatdly getting tle on 8th test case..
what is this??

Abhishek Agrawal: 2013-09-04 04:42:20

problem id:9560169 pls tell whats wrong with dis

|| तपस् ||: 2013-09-04 04:42:20

finally got AC :)
after about 20 WA

Re: Well Done , I would advice you to attempt it's harder version POWPOW2.

Last edit: 2013-06-02 17:45:01
pankaj bhardwaj: 2013-09-04 04:42:20

repeatdlygetting WA on 8th test case
what is that one must be very tricky

Re: I think you are not correct with your Logic.I will advice you to write a brute force code and see it.
edit ->thanks admin nice question take down a lot

Last edit: 2013-06-20 02:11:50
Blasters: 2013-09-04 04:42:20

devendra pl check my sol I D no 9192937 cant find any mistake

Last edit: 2013-05-02 17:39:29
Ouditchya Sinha: 2013-09-04 04:42:20

Some test cases please, I'm getting WA again & again...
Thank You for your help.
Never mind, I found it... Awesome problem. :)


RE:Thanks for the complement :)

Last edit: 2013-03-20 13:48:26
abhiranjan: 2013-09-04 04:42:20

Time limit is too strict for non-imperative languages.

We can have 1 more second to spare. :)

devu: 2013-09-04 04:42:20

To all the user:After solving this,please look after solving its improved version
http://www.spoj.pl/problems/POWPOW2/


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