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≤T≤10000) que indica la cantidad de casos. Cada caso es descrito por un entero N (1≤N≤1015) 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