問題文

正整数 $N$ と、正整数列 $A_1,A_2,...,A_N$ が与えられます。$1$ 以上 $N$ 以下の正整数 $k$ に対してそれぞれ以下の問題を解いてください。

正整数列 $A$ から要素 $A_k$ を抜いた長さ $N-1$ の正整数列 $B_1,B_2,...,B_{N-1}$ があります。 以下の条件を満たすような長さ $N-1$ の非負整数列 $C_1,C_2,...,C_{N-1}$ の個数を $1000000007$ で割った余りを求めてください。

• $1$ 以上 $N-1$ 以下の全ての正整数 $k$ に対して、$0 \le C_k < B_k$ が成り立つ。
• $|C_i-C_j|$ が $\gcd (B_i,B_j)$ の倍数でないような正整数の組 $i,j$ が存在する。

入力

$N$
$A_1$ $A_2$ $...$ $A_N$

• 入力は全て整数である。
• $3 \le N \le 10^5$
• $1 \le A_i \le 10^6$

出力

出力は $N$ 行に渡ります。$i$ 行目には、$k=i$ の時の解答を出力してください。それぞれの $k$ ごとに改行してください。

サンプル

5
12 25 65 13 10

210600
100620
35100
191100
249600

8
23 34 56 54 32 345 1234 10000

805897433
638893145
147150806
445699120
779100510
667649791
907392524
790245744