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.