CF1423J.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!

“泡沫杯”猜想已悬而未决长达 $130$ 年。任何证明该猜想的人，都将被视为我们这个时代最伟大的数学家之一！著名数学家 Jerry Mao 成功地将该猜想简化为如下问题：

给定一个数 $m$，有多少个多项式 $P$，其系数均取自集合 $\{0,1,2,3,4,5,6,7\}$，且满足 $P(2)=m$？

请帮助 Jerry Mao 解决这一久负盛名的难题！

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

第一行包含一个整数 $t$（$1 \leq t \leq 5\cdot 10^5$），表示测试用例的数量。

下一行包含 $t$ 个数 $m_i$（$1 \leq m_i \leq 10^{18}$），表示在第 $i$ 个测试用例中，你需要对数字 $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$.

对于每个测试用例 $i$，请在单独一行输出答案：即满足题面所述条件且满足 $P(2)=m_i$ 的多项式 $P$ 的个数，对 $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$.

第一种情况，当 $m=2$ 时，满足约束条件的多项式为 $x$ 和 $2$。

第二种情况，当 $m=4$ 时，满足约束条件的多项式为 $x^2$、$x + 2$、$2x$ 和 $4$。