Problems
a^b^c
a^b^c
Find the value of
$$
a^{b^c} (mod~10^9 + 7)
$$
\InputFile
The first line contains the number of test cases $n$. Each of the next $n$ lines contains three numbers $a, b, c~(a, b, c \le 10^9)$.
\OutputFile
For each test case print in a separate line the value of $a^{b^c} (mod~10^9 + 7)$.
Input example #1
3 3 7 1 15 2 2 3 4 5
Output example #1
2187 50625 763327764