I Dont Like Polynomial

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:

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

Input	Output
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".