Problem Statement

You are given a positive integer $N$ and a sequence of positive integers $A_1,A_2,...,A_N$. Solve the following problem for each positive integer $k$ between $1$ and $N$, inclusive.

There is a sequence of positive integers $B_1,B_2,...,B_{N-1}$ of length $N-1$, obtained by removing the element $A_k$ from the sequence of positive integers $A$. Find the number, modulo $1000000007$, of sequences of non-negative integers $C_1,C_2,...,C_{N-1}$ of length $N-1$ that satisfy the following conditions.

• For every positive integer $k$ between $1$ and $N-1$, inclusive, $0 \le C_k < B_k$ holds.
• There exists a pair of positive integers $i,j$ such that $|C_i-C_j|$ is not a multiple of $\gcd (B_i,B_j)$.

Input

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

• All inputs are integers.
• $3 \le N \le 10^5$
• $1 \le A_i \le 10^6$

Output

The output consists of $N$ lines. On the $i$-th line, print the answer for $k=i$. Print a newline for each $k$.

Sample

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