AT_tkppc4_1_g バラバラ掛け算

[problemUrl]: https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_g 以下の $ 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 $ で割ったあまりを出力することに注意してください。

入力は以下の形式で標準入力から与えられます。 > $ Q $ > $ N_1 $ $ N_2 $ $ \ldots $ $ N_{Q-1} $ $ N_Q $

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

### 制約 - 入力は全て整数である。 - $ 1\ \leq\ Q\ \leq\ 10^5 $ - $ 0\ \leq\ N_i\ \leq\ 10^{18} $ ### Sample Explanation 1 $ N_i\ =\ 3 $ の場合、例えば $ A\ = $ {$ 3 $} という数列のポイントは $ 3 $ であり、これが最大です。 $ N_i\ =\ 4 $ の場合、例えば $ A\ = $ {$ 2,\ 2 $} という数列のポイントは $ 2\ \times\ 2\ =\ 4 $ であり、これが最大です。