a^b^c

Input

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

For each test case print in a separate line the value of a^{b^c} \pmod{10^9 + 7}.

Examples