Matcom Online Grader

Fito está implementando un Tetris para su teléfono. En la pantalla de su teléfono Fito puede dibujar un área de 2XN con dos tipos de figuras como las que se muestra en la imagen:

La primera pieza tiene dimensión de 1X2 y la otra figura con forma de L tiene en una "pata" dimensión de 2X1 y en la otra 3X1. Cada pieza puede ser rotada/invertida en cualquier dirección para ser ubicada en la pantalla. Fito está calculando un sistema de puntuación para su juego y necesita saber de cuantas formas se puede cubrir la pantalla usando estas dos piezas, como este número puede ser grande la respuesta se debe dar con módulo 10^9+7.

Input

En la primera línea de la entrada se encuentra un numero T (1<=T<=1000) que representa la cantidad de casos de prueba. Luego por cada caso de prueba en una línea hay un entero N (1<=N<= 1000000).

Output

Sample test(s)