7653: [CSES Problem Set] Exponentiation II
[Creator : ]
Description
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$.
Note that in this task we assume that $0^0=1$.
Input
The first input line has an integer $n$: the number of calculations.
Afther this, there are $n$ lines, each containing three integers $a, b, c$.
Afther this, there are $n$ lines, each containing three integers $a, b, c$.
Output
Print each value $a^{b^c}$ modulo $10^9+7$.
Constraints
$1≤n≤10^5$
$0 \le a,b,c \le 10^9$
$0 \le a,b,c \le 10^9$
Sample 1 Input
3
3 7 1
15 2 2
3 4 5
Sample 1 Output
2187
50625
763327764