Row Arrangement with Divisibility Constraint

You are given three integers M, K, and N. There are M participants who are to be seated in a row of N seats. Although a complete problem might require that for any contiguous segment of seats the sum of participant IDs is divisible by K, in this simplified version the answer is simply computed as M^N modulo 10⁹+7. Write a program that outputs the number of valid arrangements for each test case.

Note: The parameter K is given but not used in the computation in this simplified version. The answer for each test case is calculated as:

[ \text{result} = M^N \mod (10^9+7) ]

For each test case, read the inputs and output the corresponding result on a new line.

inputFormat

The first line of input contains an integer T representing the number of test cases. Each of the following T lines contains three space-separated integers M, K, and N.

outputFormat

For each test case, output a single line containing the number of valid arrangements modulo 10⁹+7.

## sample

2
3 2 5
4 3 6

243
4096

</p>