67 . 整數分拆
Description
整數分拆是離散數學中相當有名的一類問題。我們可以將一個正整數 $x$ 寫成若干個正整數的和，例如 $7$ 可以被寫為 $1+1+2+3$ 或者 $2+2+3$ 等等。
數學家們可能會討論總共有幾種符合條件的分拆方式，或者哪一種分拆方式做為某個函數的輸入可以獲得極值。
在這個問題中，我們想要討論一個整數的「分拆積」，也就是將分拆後的所有數值相乘獲得的乘積。
舉例來說，考慮 $x = 5$ 的情況，若我們只考慮分拆項整數非嚴格遞增的情況，一共會有下列七種分拆方式：
1. $1+1+1+1+1$，其分拆積為 $1 \times 1 \times 1 \times 1 \times 1 = 1$
2. $1+1+1+2$，其分拆積為 $1 \times 1 \times 1 \times 2 = 2$
3. $1+2+2$，其分拆積為 $1 \times 2 \times 2 = 4$
4. $1+1+3$，其分拆積為 $1 \times 1 \times 3 = 3$
5. $2+3$，其分拆積為 $2 \times 3 = 6$
6. $1+4$，其分拆積為 $1 \times 4 = 4$
7. $5$，其分拆積為 $5$
我們將這些分拆積中最大的數值稱為「最大分拆積」，以上例來說當 $x = 5$ 時「最大分拆積」即是 $6$（使用 $2+3$ 的分拆方式）。
請寫一支程式計算一個整數「最大分拆積」。由於該數字可能會很大，請輸出該數值除以 ($10$$9$ $+ 7$) 的餘數。
對於所有測試資料：
$1 \le T \le 10$$4$
$1 \le x \le 10$$9$
Input Format
第一行有一個整數 $T$ 代表有幾筆詢問資料。
接下來有 $T$ 行，每一行有一個整數 $x$，即是想查詢的整數。
Output Format
輸出 $T$ 行，每一行一個整數，依序為輸入中每一筆查詢的「最大分拆積」除以 ($10$$9$ $+ 7$) 的餘數。
Sample Input 1
6 1 5 15 679 10000 1000000000
Sample Output 1
1 6 243 662554012 515481589 897135186
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測試資料 | 0 |
| 2 | 1~10 | $T = 1$ 且 $x \le 10$$5$ | 80 |
| 3 | 0~20 | 無額外限制 | 20 |