D - Tres vecinos

Time limit: 10 seconds
Memory limit: 256 megabytes
Languages: MS C# .NET 4.7.2053,GNU G++11 5.1.0 ...

En una calle hay $N$ casas una al lado de la otra y se quiere saber de cuántas formas es posible seleccionar un subconjunto de estas, que cumpla que al menos $3$ casas contiguas están en el subconjunto.

Input

La primera línea de la entrada es un entero $T$ $(1 \leq T \leq 10000)$ que indica la cantidad de casos. Cada caso es descrito por un entero $N$ $(1 \leq  N \leq 10^{15}) $ en una línea.

Output

Por cada caso se debe imprimir una línea con la cantidad de formas de seleccionar las casas cumpliendo el requisito mencionado.  Como este número puede ser muy grande se debe imprimir el resto de su división por $1,000,000,007$.

Sample test(s)

Input
2 3 4
Output
1 3