POWRTU - Power with Combinatorics(EASY)

no tags 

Your task is to calculate a^(b^(exp))

a:provided in input,500=>a>=0

b:provided in input,500=>b>=0

exp=(nC0)^2 + (nC1)^2 + (nC2)^2 + ......+(nCn)^2

n:provided in input,500=>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.

Click here to see my set of problems at Spoj.


hide comments
Abhishek: 2016-09-27 10:20:18

Fun Problem!, 500000002 is the golden number for this!

Mayank Ladia: 2014-12-27 17:28:17

Last edit: 2015-07-16 16:57:05

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