Bubble Cup hypothesis

1000ms

262144K

Description:

The Bubble Cup hypothesis stood unsolved for $$$130$$$ years. Who ever proves the hypothesis will be regarded as one of the greatest mathematicians of our time! A famous mathematician Jerry Mao managed to reduce the hypothesis to this problem:

Given a number $$$m$$$, how many polynomials $$$P$$$ with coefficients in set $$${\{0,1,2,3,4,5,6,7\}}$$$ have: $$$P(2)=m$$$?

Help Jerry Mao solve the long standing problem!

Input:

The first line contains a single integer $$$t$$$ $$$(1 \leq t \leq 5\cdot 10^5)$$$ - number of test cases.

On next line there are $$$t$$$ numbers, $$$m_i$$$ $$$(1 \leq m_i \leq 10^{18})$$$ - meaning that in case $$$i$$$ you should solve for number $$$m_i$$$.

Output:

For each test case $$$i$$$, print the answer on separate lines: number of polynomials $$$P$$$ as described in statement such that $$$P(2)=m_i$$$, modulo $$$10^9 + 7$$$.

Sample Input:

2
2 4

Sample Output:

2
4

Note:

In first case, for $$$m=2$$$, polynomials that satisfy the constraint are $$$x$$$ and $$$2$$$.

In second case, for $$$m=4$$$, polynomials that satisfy the constraint are $$$x^2$$$, $$$x + 2$$$, $$$2x$$$ and $$$4$$$.

Informação

Provedor Codeforces

Código CF1423J