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.

Click here to see my set of problems at Spoj.


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

hide comments
2013-09-04 04:42:20 Rajesh Kumar
huuhhhh... Finally DOne...
After about 10 WA's..
NicE Question :)

Re:Thanks for ur appreciation,u may now try for the harder version, http://www.spoj.pl/problems/POWPOW2/

Last edit: 2012-07-16 13:30:27
2013-09-04 04:42:20 Shaily Mittal
Can you provide some more test cases for big values og a,b and n?

Re:Write a brute force code and find it for yourself. :)

Last edit: 2012-07-16 04:45:37
2013-09-04 04:42:20 Himanshu Srivastava
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
2013-09-04 04:42:20 Mitch Schwartz
@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
2013-09-04 04:42:20 devu
@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.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.