Description

H 教授是一位密码学专家，他现在正在研究如何对一个正整数做特殊分解，因而发明了正整数的回文分解法，其分解方法如下：对于一个正整数 $n$，把 $n$ 分解成 $k$ 个正整数 $x_1, x_2, \ldots, x_k$ 的和，满足 $n = x_1 + x_2 + \ldots + x_k$，且 $x_1, x_2, \ldots, x_k$ 由左读到右和由右读到左相同。

当两种分解法分解出来的正整数数量不同，或者出现的次序不同时，则视为不同的分解法。更严谨地说，设 $n = a_1 + a_2 + \ldots + a_k = b_1 + b_2 + \ldots + b_l$ 为两种回文分解法。若 $k \ne l$，或者 $k = l$ 但存在 $i \in \{1, 2, \ldots, k\}$ 使得 $a_i \ne b_i$，则视为不同的分解法。例如正整数 $6$ 有 $8$ 种回文分解法，分别是

1. $6$；
2. $2 + 2 + 2$；
3. $3 + 3$；
4. $2 + 1 + 1 + 2$；
5. $1 + 4 + 1$；
6. $1 + 1 + 2 + 1 + 1$；
7. $1 + 2 + 2 + 1$；
8. $1 + 1 + 1 + 1 + 1 + 1$。

给定一个正整数 $n$，请写一个计算机程序去计算 $n$ 有多少种不同的回文分解法。因为这个数字可能很大，你只要求出方法数除以 $10^9 + 7$ 的余数就行了。

Input Format

$t$
$n_1$
$n_2$
$\vdots$
$n_t$

• $t$ 代表你的计算机程序需要处理的正整数 $n$ 的个数。
• $n_i$ 代表第 $i$ 笔询问的正整数 $n$。

Output Format

$\textrm{ans}_1$
$\textrm{ans}_2$
$\vdots$
$\textrm{ans}_t$

• $\textrm{ans}_i$ 代表 $n_i$ 的回文分解方法数除以 $10^9 + 7$ 的余数。

2
3
6

2
8

Hint

测试数据限制

• $1 \le t \le 10^4$。
• $1 \le n_i \le 10^{15}$。
• 输入的数皆为整数。

评分说明

本题共有四组子任务，条件限制如下所示。 每一组可有一或多个测试数据，该组所有测试数据皆需答对才可获得该组分数。