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 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.
hide comments
sankalp_7:
20210709 19:41:28
What is there in test case 8 :(


abhinav_jain02:
20190615 09:08:12
Pre requisites:


kmkhan_014:
20180509 06:01:44
Anyone please comment the result for:


yash_code_guy:
20170110 03:39:44
Wow What a question


Tanzir Islam:
20150720 15:53:13
I got ac in this problem. However, there's something weird about this problem.


Sayak Haldar:
20150125 14:59:55
@psetter, is 0^0=1? like in powpow2 and tutorial version of it?


i need you:
20141210 16:44:28
getting wrong answer in 8th judge...please suggest


Mayank Ladia:
20141130 17:34:32
testcase 8.. WA now :( Last edit: 20150713 23:02:16 

tapan sahni:
20140728 15:37:21
getting nzec in java ...what to do 

kancha:
20131220 18:16:33
testcase 8 is killing me now :(

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