Migrated from Lutece 1053 GCD

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

There is a sequence which has $n$ elments. Each element of the sequence is ranged in $[1, n]$. Now Alice is wondering for each $k (1 \leq k < n)$, how many solutions for she to choose $k$ elements from the sequence so that the greatest common divisor of them is no more than $n - k$.

As is known to everyone of you, Bob loves Alice very much. Could you tell Bob the answers to help Bob leave a good impression on Alice.

Input

The first line contains an integer $n$, indicating the number of the elements in the sequence.

The next line contains $n$ integers $a_i$, indicating the element in the sequence.

It is guaranteed that $1 \leq a_i \leq n \leq 100000$.

Output

Print $n - 1$ lines. For each $k (1 \leq k < n)$, the $k_{th}$ line contains the number of solutions for Alice to choose $k$ elements from the sequence, so that the greatest common divisor of them is no more than $n - k$. The answer be moduled by 1000000007.

Samples

3
2 2 3

2
2

Resources

The 13th UESTC Programming Contest Final