POWPOW  Power with Combinatorics
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.
hide comments
Amitayush Thakur:
20131102 15:28:14
Got AC after 18 attempts!!!


Himanshu:
20130914 12:46:01
repeatdly getting tle on 8th test case..


Abhishek Agrawal:
20130904 04:42:20
problem id:9560169 pls tell whats wrong with dis 

 तपस् :
20130904 04:42:20
finally got AC :)


pankaj bhardwaj:
20130904 04:42:20
repeatdlygetting WA on 8th test case


Blasters:
20130904 04:42:20
devendra pl check my sol I D no 9192937 cant find any mistake Last edit: 20130502 17:39:29 

Ouditchya Sinha:
20130904 04:42:20
Some test cases please, I'm getting WA again & again...


abhiranjan:
20130904 04:42:20
Time limit is too strict for nonimperative languages.


devu:
20130904 04:42:20
To all the user:After solving this,please look after solving its improved version


Rajesh Kumar:
20130904 04:42:20
huuhhhh... Finally DOne...

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