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 conating 3 integers,(i.e a b n  in order) each of them seperated by a space.

Output

Output Contains t lines,ith line conatins 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
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/

Rajesh Kumar: 2013-09-04 04:42:20

huuhhhh... Finally DOne...
After about 10 WA's..
NicE Question :)

Re:Thanks for ur appreciation,u may now try for the harder version, http://www.spoj.pl/problems/POWPOW2/

Last edit: 2012-07-16 13:30:27

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