El granjero Harry ha comprado recientemente 3 tipos de flores para plantarlas en su casa. Esas 3 flores son de color Rojo, Verde y Azul.

Como todos saben el jardín de Harry es mágico. Esto significa que si plantas un cierto número de flores un día al próximo este se incrementara.

El jardín incrementa el número de flores de acuerdo a su color, esto va así:

-Si tu plantas una flor roja un día, este se convertirá en 6 flores al próximo día. (1 roja, 2 verdes y 3 azules).

-Si tu plantas una flor verde un día, luego esta se convertirá en 15 flores, (4 rojas, 5 verdes y 6 azules).

-Si tu plantas una flor azul un día, luego esta se convertirá en 24 flores (7 rojas, 8 verdes y 9 azules).

Como se menciono antes, el granjero Harry tiene al principio una flor roja, una azul y una verde. Y el pide tu ayuda para que le digas el número total de flores que tendrá su jardín el n-esimo día.

La primera línea de entrada contiene T el número de casos de prueba (1<=T<=1000). Cada caso de prueba contiene un único número N (1<=N<=10⁹) que indica el n-esimo día.

Para cada caso de prueba, imprima un entero conteniendo el número total de flores en el jardín mágico el n-esimo día modulo 1000000007.