A13820. Bubble Cup hypothesis

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!

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$ .

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$ .

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$ .