Problems
a^b^c
a^b^c
Find the value of
a^{b^c} (mod~10^9 + 7)
Input data
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).
Output data
For each test case print in a separate line the value of a^{b^c} (mod~10^9 + 7).
Examples
Input example #1
3 3 7 1 15 2 2 3 4 5
Output example #1
2187 50625 763327764