## POWPOW - Power with Combinatorics

no tags

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 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.`

 < Previous 1 2 3 Next > Himanshu Srivastava: 2013-09-04 04:42:20 is there any special case....why i get wrong answer at running judge 8?? Re:No Special test cases at all.. Last edit: 2012-07-15 18:21:55 Mitch Schwartz: 2013-09-04 04:42:20 @Devendra: Thanks for your response. But for me the original version of the problem is more interesting. I don't know how you feel about it -- whether you would be willing to change it back to a^b^exp (but with corrected test data), or maybe have a^b^exp version added as a separate problem. If you can't solve a^b^exp version at this time, maybe I could add it (I haven't solved it yet, but I know a way), although I prefer to be able to compete on it. Also I think it's worth reiterating Francky's earlier comment about whether the time limit is appropriate for slower languages like Python. What do you think? Re:Earlier Version of the problem is added ,u can attempt it http://www.spoj.pl/problems/POWPOW2/ Last edit: 2012-07-14 16:43:23 devu: 2013-09-04 04:42:20 @Francky,Mitch Schwartz:Thanks for pointing out the error,actually i thought for a^(exp^b) bt what lead me to calculate a^(b^exp) with same logic has no explanation,I apologize to all the users who put up their valuable time to solve that one,I hope that this one is a correct one.