G - バラバラ掛け算 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 300

問題文

以下の Q 個のクエリに答えてください。

  • i 番目のクエリでは、整数 N_i が与えられる。
  • 長さ M (M \geq 1) の整数列 A = {A_1, A_2, ..., A_M} において、そのポイントを A_1 \times A_2 \times ... \times A_{M-1} \times A_M とする。
  • A_1 + A_2 + A_3 + ... + A_M = N_i かつ A_j\geq 0 を満たす整数列の中でのポイントの最大値を 10^{9}+7 で割ったあまりを出力する。

ただし、ポイントを 10^{9}+7 で割ったあまりの最大値ではなく、ポイントの最大値を 10^{9}+7 で割ったあまりを出力することに注意してください。

制約

  • 入力は全て整数である。
  • 1 \leq Q \leq 10^5
  • 0 \leq N_i \leq 10^{18}

入力

入力は以下の形式で標準入力から与えられます。

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

出力

それぞれのクエリの答えを順に、空白区切りで出力してください。


入力例1

2
3 4

出力例1

3 4

N_i = 3 の場合、例えば A = {3} という数列のポイントは 3 であり、これが最大です。

N_i = 4 の場合、例えば A = {2, 2} という数列のポイントは 2 \times 2 = 4 であり、これが最大です。

writer: define