Tu tarea consiste en calcular eficientemente los valores ~a^{b^c}~ módulo ~10^9+7~. Ten en cuenta que en esta tarea suponemos que ~0^0=1~.

Entrada

La primera línea de entrada contiene un número entero ~n~: el número de cálculos.

Después, hay ~n~ líneas, cada una con tres enteros ~a, b~ y ~c~.

Salida

Imprime cada valor ~a^{b^c}~ módulo ~10^9+7~.

Restricciones

• ~1 \leq n \leq 10^5~.
• ~0 \leq a,b,c \leq 10^9~.

Ejemplo de Entrada

3
3 7 1
15 2 2
3 4 5

Ejemplo de Salida

2187
50625
763327764