I Dont Like Polynomial

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

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

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:

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

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

Input

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

Output

For each test case ii, print the answer modulo 109+710^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 i=jkf(i)\sum_{i=j}^{k}{f(i)} means f(j)+f(j+1)+f(j+2)+...+f(k1)+f(k)f(j)+f(j+1)+f(j+2)+...+f(k-1)+f(k). x\lfloor x \rfloor means “largest integer which is smaller than or equal to x".

Submit

Login to submit.

Statistics

12% Solution Ratio
Tahmid690Earliest, Oct '20
fsshakkhorFastest, 0.0s
fsshakkhorLightest, 1.0 MB
Tahmid690Shortest, 1236B
Toph uses cookies. By continuing you agree to our Cookie Policy.