Tu tarea consiste en calcular eficientemente los valores ~a^b~ módulo ~10^9+7~.

Ten en cuenta que en esta tarea asumimos 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 de las cuales contiene dos enteros ~a~ y ~b~.

Salida

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

Restricciones

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

Ejemplo de Entrada

3
3 4
2 8
123 123

Ejemplo de Salida

81
256
921450052