Alice has n+1 items. The items have ids from 1 to n. This means there could be multiple

same ids. And it is also known that each of the items id 1 to n appears at least once in the

sequence.

Now Alice is fond of sequences. She wants to find for each integer k = 1 to n+1, the number

of subsequences of the given sequence of item ids with length k, mod 10ˆ9 + 7.

Constraints:

1 <= n <= 10^5

Input Format

The first line contains an integer n. The second line contains n+1 integers denoting the sequence of integers where each integer is between 1 and n.

Output Format

Print n+1 lines. The kth line should contain the number of different sub-sequences of the given sequence, in the same order, with length k, mod 10ˆ9 + 7.

PS: Sample test cases are different than the ones your code is evaluated on after your submission. Hence, sample #0 at the time of running your code and Testcase #0 at the time of submission will be different.

Sample input1

3

1 2 1 3

op1

3

5

4

1

sample input2

2

1 2 1

op2

2

3

1