Problem Statement

You are given an integer sequence of length $n+1$, $a_1,a_2,...,a_{n+1}$, which consists of the $n$ integers $1,...,n$. It is known that each of the $n$ integers $1,...,n$ appears at least once in this sequence.

For each integer $k=1,...,n+1$, find the number of the different subsequences (not necessarily contiguous) of the given sequence with length $k$, modulo $10^9+7$.

Note

• If the contents of two subsequences are the same, they are not separately counted even if they originate from different positions in the original sequence.
• A subsequence of a sequence $a$ with length $k$ is a sequence obtained by selecting $k$ of the elements of $a$ and arranging them without changing their relative order. For example, the sequences $1,3,5$ and $1,2,3$ are subsequences of $1,2,3,4,5$, while $3,1,2$ and $1,10,100$ are not.

Constraints

• $1 \leq n \leq 10^5$
• $1 \leq a_i \leq n$
• Each of the integers $1,...,n$ appears in the sequence.
• $n$ and $a_i$ are integers.

Input

Input is given from Standard Input in the following format:

n
a_1 a_2 ... a_{n+1}

Output

Print $n+1$ lines. The $k$-th line should contain the number of the different subsequences of the given sequence with length $k$, modulo $10^9+7$.