Bubble Cup hypothesis

#### 题目描述 给定正整数 $m$,求有多少不同的多项式 $P$ 使得: 1. $P(2)=m$. 2. 对于多项式 $P$ 任意一项的系数 $i$ 有: $i$ 为整数且$0 \leq i \leq 7$. 输出答案对$10^9+7$取模后的值. #### 输入与输出格式 第一行输入一个整数 $T(1 \leq T \leq 500,000)$ 表示测试数据个数 接下来一行将会输入 $T$ 个数字 $m_{i}(1 \leq m_{i} \leq 1e18)$,表示在第 $i$ 项测试数据你应解决关于 $m_{i}$ 的问题. 对于第 $i$ 项测试数据,输出当 $m=m_{i}$ 时满足上述要求的多项式 $P$ 的数量对$10^9+7$取模后的值. #### 样例解释 对于第一个测试数据,满足要求的多项式有: $2$ 和 $x$; 对于第二个测试数据,满足要求的多项式有: $4$ , $2x$ , $x+2$ , $x^2$.

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

2
2 4

2
4

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