POWPOW2 - Power with Combinatorics(HARD)

no tags 

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

Click here to see my set of problems at Spoj.


hide comments
nitish_prasad: 2020-04-10 03:26:49

gud question

saurav_555: 2020-01-26 10:36:24

Please don't refer to the github code , for checking your code....
Because it contain wrong answers....
ex. for test case 10 10 10
it gives...669572223
but actual answer is ...330427784

Last edit: 2020-01-26 11:48:26
kmkhan_014: 2018-05-09 06:27:15

what is the output for:
1
2 2 2

Francky: 2017-02-10 19:09:38

Now doable using Python3.

rahul_985: 2017-01-24 15:14:05

can't pass test # 8 , tried all base case with 0^0;
plz.. can anybody help me ??

a_thinker: 2016-07-10 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: 2016-07-10 18:50:30

@Francky please all the tell the answer of your proposed testcases ?

a_thinker: 2016-07-10 18:04:16

in this problem do we need to take c(0,0) as 1 or 0 ?
it needs to be taken as 1

Last edit: 2016-07-10 19:28:03
livmic: 2016-03-22 19:32:43

i think your test cases with n=0 have wrong results

livmic: 2016-03-22 17:19:49

i cant understand why i m getting WA...
everything seems to work correctly....


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