AT_tkppc4_1_g.バラバラ掛け算

请回答以下 $Q$ 个查询。

• 第 $i$ 个查询会给出一个整数 $N_i$。
• 对于长度为 $M$（$M \geq 1$）的整数序列 $A = \{A_1, A_2, \ldots, A_M\}$，其得分定义为 $A_1 \times A_2 \times \ldots \times A_{M-1} \times A_M$。
• 在所有满足 $A_1 + A_2 + \ldots + A_M = N_i$ 且 $A_j \geq 0$ 的整数序列中，输出得分的最大值对 $10^9+7$ 取模的结果。

请注意，要求输出的是最大得分对 $10^9+7$ 取模的结果，而不是对 $10^9+7$ 取模后的最大值。

输入通过标准输入给出，格式如下：

$Q$
$N_1$ $N_2$ $\ldots$ $N_{Q-1}$ $N_Q$

请依次输出每个查询的答案，使用空格分隔。

限制条件

• 所有输入均为整数。
• $1 \leq Q \leq 10^5$
• $0 \leq N_i \leq 10^{18}$

样例解释 1

当 $N_i = 3$ 时，例如 $A = \{3\}$ 这个序列的得分为 $3$，这是最大值。当 $N_i = 4$ 时，例如 $A = \{2, 2\}$ 这个序列的得分为 $2 \times 2 = 4$，这是最大值。

由 ChatGPT 4.1 翻译