P11909 [NHSPC 2023] H. 整数的回文分解法

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$ 的余数就行了。

> $t$ > $n_1$ > $n_2$ > $\vdots$ > $n_t$ * $t$ 代表你的计算机程序需要处理的正整数 $n$ 的个数。 * $n_i$ 代表第 $i$ 笔询问的正整数 $n$。

> $\textrm{ans}_1$ > $\textrm{ans}_2$ > $\vdots$ > $\textrm{ans}_t$ * $\textrm{ans}_i$ 代表 $n_i$ 的回文分解方法数除以 $10^9 + 7$ 的余数。

### 测试数据限制 * $1 \le t \le 10^4$。 * $1 \le n_i \le 10^{15}$。 * 输入的数皆为整数。 ### 评分说明 本题共有四组子任务，条件限制如下所示。 每一组可有一或多个测试数据，该组所有测试数据皆需答对才可获得该组分数。 | 子任务 | 分数 | 额外输入限制 | | :------: | :----: | ------------ | | 1 | $10$ | 输入的 $n_i$ 两两相异，且 $n_i \le 30$ | | 2 | $30$ | $n_i \le 1000$ | | 3 | $10$ | $n_i \le 10^6$ | | 4 | $50$ | 无额外限制 |