POWPOW2  Power with Combinatorics(HARD)
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 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^(1^2) is 1,so output is 1.
Note: First try out the tutorial version where limits are low. POWRTU
hide comments
nitish_prasad:
20200410 03:26:49
gud question 

saurav_555:
20200126 10:36:24
Please don't refer to the github code , for checking your code....


kmkhan_014:
20180509 06:27:15
what is the output for:


Francky:
20170210 19:09:38
Now doable using Python3. 

rahul_985:
20170124 15:14:05
can't pass test # 8 , tried all base case with 0^0;


a_thinker:
20160710 19:27:26
for those struggling with test case 7 or 8 and getting everything correct, then most probably u won't get what needs to be done by debuging , just try to make ur code more stronger and read the comments. 

a_thinker:
20160710 18:50:30
@Francky please all the tell the answer of your proposed testcases ? 

a_thinker:
20160710 18:04:16
in this problem do we need to take c(0,0) as 1 or 0 ?


livmic:
20160322 19:32:43
i think your test cases with n=0 have wrong results


livmic:
20160322 17:19:49
i cant understand why i m getting WA...

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