# I Dont Like Polynomial

Father Timm Memorial Prog...
Limits 1s, 512 MB

Given a $k$ degree polynomial $P(x)=\sum_{i=0}^{k}{a_ix^i}$ ($0 \leq a_i\leq 7$) and $f(n)=\text{“number of such polynomial so that }P(2)=n\text{"}$, find $\sum_{i=0}^{m}{f(i)}$ for a given number $m$.

I found this problem in an online contest. But it was very tough for me to solve. Luckily I found a solution pattern for this problem generating solution for some small test cases. I found that:

$\Large{f(n)=\lfloor \frac{\lfloor \frac{n+4}{2} \rfloor ^{2}}{4} \rfloor}$

But still, I can't find $\sum_{i=0}^{m}{f(i)}$. So please help me out.

## Input

The first line contains a single integer $t$ ($1\leq t\leq 10^5$) number of test cases. On next line there are $t$ numbers, $m_i$($0\leq m\leq 10^{18}$) meaning that in case $i$ you should solve for number $m_i$.

## Output

For each test case $i$, print the answer modulo $10^9+7$ on separate lines.

## Sample

InputOutput
4
1 2 3 4

2
4
6
10


for the second test case :

$f(0)=1$ because there is only one polynomial for which $P(2)=0$ and the polynomial is $P(x)=0\times x^0$

$f(1)=1$ because there is only one polynomial for which $P(2)=1$ and the polynomial is $P(x)=1\times x^0$

$f(2)=2$ because there is two such polynomial for which $P(2)=2$ and the polynomials are $P(x)=2\times x^0$ and $P(x)=0\times x^0+1\times x^1$

Hence $\sum_{i=0}^{2}{f(i)}=1+1+2=\boxed{4}$

Here $\sum_{i=j}^{k}{f(i)}$ means $f(j)+f(j+1)+f(j+2)+...+f(k-1)+f(k)$. $\lfloor x \rfloor$ means “largest integer which is smaller than or equal to x".