题目描述

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$ 的餘數。

2
3
6

2
8

提示

測資限制

• $1 \le t \le 10^4$。
• $1 \le n_i \le 10^{15}$。
• 輸入的數皆為整數。

評分說明

本題共有四組子任務，條件限制如下所示。 每一組可有一或多筆測試資料，該組所有測試資料皆需答對才會獲得該組分數。