e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

Euler Function

a^b^c

Find the value of

prb9627.gif

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