a^b^c

Find the value of

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}(mod10^9+7)$.

Examples