Your task is to efficiently calculate values $a^{b^c}$ modulo $10^9+7$ .
Note that in this task we assume that $0^0=1$ .
The first input line has an integer $n$ : the number of calculations.
After this, there are $n$ lines, each containing three integers $a$ , $b$ and $c$ .
Print each value $a^{b^c}$ modulo $10^9+7$ .
3 3 7 1 15 2 2 3 4 5\n · · \n · · \n · · \n
2187 50625 763327764\n \n \n