Competitions

a^b^c

Find the value of

Input

First line contains the number of test cases n. Each of the next n lines contains three numbers a, b, c (a, b, c109).

Output

For each test case print in a separate line the value of a^b^c (mod 109 + 7).

Time limit 1 second
Memory limit 128 MiB
Input example #1
3
3 7 1
15 2 2
3 4 5

Output example #1
2187
50625
763327764

Author Mykhailo Medvediev