POWPOW - Power with Combinatorics

no tags 

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

Click here to see my set of problems at Spoj.


hide comments
kmkhan_014: 2018-05-09 06:01:44

Anyone please comment the result for:
1
2 2 2

yash_code_guy: 2017-01-10 03:39:44

Wow What a question
My 50th :)

Last edit: 2017-01-21 14:41:57
Tanzir Islam: 2015-07-20 15:53:13

I got ac in this problem. However, there's something weird about this problem.
In my solution, I wrote the function to calculate power like this,
long long power(long long a, long long b, long long p)
{
if(a == 0)
return 0;
......
}
I got wa. Then I removed this if condition, I got ac. 0^b should be 0 for any value of b, shouldn't it ?

Sayak Haldar: 2015-01-25 14:59:55

@psetter, is 0^0=1? like in powpow2 and tutorial version of it?
edit 1: anyone who solves this problem, please help me by giving the answer..

Last edit: 2015-01-25 15:39:21
i need you: 2014-12-10 16:44:28

getting wrong answer in 8th judge...please suggest
edit-done!

Last edit: 2015-02-02 11:29:09
Mayank Ladia: 2014-11-30 17:34:32

testcase 8.. WA now :(

Last edit: 2015-07-13 23:02:16
tapan sahni: 2014-07-28 15:37:21

getting nzec in java ...what to do

kancha: 2013-12-20 18:16:33

testcase 8 is killing me now :(
feww....accepted al last!!
thanks for this problem :D

Last edit: 2013-12-20 19:09:07
Amitayush Thakur: 2013-11-02 15:28:14

Got AC after 18 attempts!!!
was getting WA for 8th test case repeatedly.
Was doing a very silly mistake :D :D

Himanshu: 2013-09-14 12:46:01

repeatdly getting tle on 8th test case..
what is this??


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