如果一个正整数多重集 $A = \{a_1, a_2, \dots, a_k\}$ 的元素之和等于 $n$，且 $1$ 到 $n$ 之间的每个整数都可以唯一地表示为 $A$ 中若干元素的和（不计顺序），则称该多重集为 $n$-handsome。例如，$\{1, 2, 4\}$ 是 $7$-handsome，$\{1, 1, 3\}$ 是 $5$-handsome。给定整数 $n$，求以下和：

$$\left( \sum_{A \text{ is } n\text{-handsome}} |A| \right) \pmod p$$

对于每个需要计算答案的 $n$，你可以自行选择 $p = 10^9 + 7$ 或 $p = 10^9 + 9$。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 5$)，表示输入文件中的测试用例数量。 接下来的 $t$ 行，每行包含一个整数 $n_i$ ($1 \le n_i \le 10^{16}$)，你需要对每个 $n_i$ 输出答案。保证同一文件中所有的 $n_i$ 均不相同。

输出格式

输出 $t$ 行。第 $i$ 行应包含对应数字 $n_i$ 的答案。每个答案在 $p = 10^9 + 7$ 或 $p = 10^9 + 9$ 下正确即可，且对于每个测试用例，$p$ 可以独立选择。注意，你不需要输出所选的 $p$，只需输出答案的余数。

样例

样例输入 1

5
1
2
3
4
5

样例输出 1

1
2
5
4
11

样例输入 2

5
6
7
8
9
10

样例输出 2

6
18
12
19
10

样例输入 3

5
99
17
14
24
38

样例输出 3

572
64
26
32
66