DA-IICT Intra Programming Contest 07

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

• 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 input, 10^5 >= 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 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^(1^2) is 1, so output is 1.

Note: First try out the tutorial version where limits are low. POWRTU

Click here to see my set of problems at SPOJ.