Tu tarea consiste en construir una torre cuyo ancho sea ~2~ y su altura sea ~n~. Dispones de una cantidad ilimitada de bloques cuya anchura y altura son números enteros. Por ejemplo, aquí tienes algunas soluciones posibles para ~n=6~:

Dado ~n~, ¿cuántas torres diferentes puedes construir? Las torres reflejadas y giradas se cuentan por separado si tienen un aspecto diferente.

Entrada

La primera línea de entrada contiene un número entero ~t~: el número de pruebas.

Después hay ~t~ líneas, y cada línea contiene un entero ~n~: la altura de la torre.

Salida

Para cada prueba, imprime el número de torres módulo ~10^9+7~.

Restricciones

• ~1 \leq t \leq 100~.
• ~1 \leq n \leq 10^6~.

Ejemplo de Entrada

3 
2
6
1337

Ejemplo de Salida

8
2864
640403945