11

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.

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.

Examples

Input

3 1 2 1 3

Output

3 5 4 1

Input

1 1 1

Output

1 1

Input

32 29 19 7 10 26 32 27 4 11 20 2 8 16 23 5 14 6 12 17 22 18 30 28 24 15 1 25 3 13 21 19 31 9

Output

32 525 5453 40919 237336 1107568 4272048 13884156 38567100 92561040 193536720 354817320 573166440 818809200 37158313 166803103 166803103 37158313 818809200 573166440 354817320 193536720 92561040 38567100 13884156 4272048 1107568 237336 40920 5456 528 33 1

inputFormat

Input

Input is given from Standard Input in the following format:

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

outputFormat

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.

Examples

Input

3 1 2 1 3

Output

3 5 4 1

Input

1 1 1

Output

1 1

Input

32 29 19 7 10 26 32 27 4 11 20 2 8 16 23 5 14 6 12 17 22 18 30 28 24 15 1 25 3 13 21 19 31 9

Output

32 525 5453 40919 237336 1107568 4272048 13884156 38567100 92561040 193536720 354817320 573166440 818809200 37158313 166803103 166803103 37158313 818809200 573166440 354817320 193536720 92561040 38567100 13884156 4272048 1107568 237336 40920 5456 528 33 1

样例

1
1 1

1
1

</p>