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$ | 無額外限制 |