气泡杯假说在 $$$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$$$。