SPOJ Brasil

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

a: provided in input, 0 ≤ a ≤ 500

b: provided in input, 0 ≤ b ≤ 500

exp = (nC0)² + (nC1)² + (nC2)² + ... + (nCn)²

n: provided in input, 0 ≤ n ≤ 500

Note: The Output for 0⁰ should be 1.

Where nCr denotes n choose r.

As the answer can be too large, you need to output modulo 10⁹+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

Write 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¹² is 1, so output is 1.

Click here to see my set of problems at SPOJ.