← 返回题目列表

Codeforces · 1423/J

J. 气泡杯假设

中文机器翻译题面 查看原题

气泡杯假说在 $$$130$$$ 年间一直没有得到解决。谁能证明这个假设,谁就会被视为我们这个时代最伟大的数学家之一!著名数学家毛杰瑞(Jerry Mao)成功地将假设简化为这个问题:

给定一个数字 $$$m$$$,有多少个系数在集合 $$${\{0,1,2,3,4,5,6,7\}}$$$ 中的多项式 $$$P$$$ 有:$$$P(2)=m$$$?

帮助Jerry Mao解决长期存在的问题!

输入

第一行包含一个整数 $$$t$$$ $$$(1 \leq t \leq 5\cdot 10^5)$$$ - 测试用例的数量。

下一行有 $$$t$$$ 数字, $$$m_i$$$ $$$(1 \leq m_i \leq 10^{18})$$$ - 意味着如果 $$$i$$$ 你应该解出数字 $$$m_i$$$。

输出

对于每个测试用例 $$$i$$$,在单独的行上打印答案:多项式 $$$P$$$ 的数量,如语句中所述,使得 $$$P(2)=m_i$$$,以 $$$10^9 + 7$$$ 为模。

示例

输入 #1

2
2 4

输出 #1

2
4

注意

在第一种情况下,对于 $$$m=2$$$,满足约束的多项式是 $$$x$$$ 和 $$$2$$$。

在第二种情况下,对于 $$$m=4$$$,满足约束的多项式为 $$$x^2$$$、$$$x + 2$$$、$$$2x$$$ 和 $$$4$$$。