11

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

给定一个长度为 $n+1$ 的整数序列 $a_1,a_2,\ldots,a_{n+1}$。序列中的数均在 $1$ 到 $n$ 之间，并且 $1,2,\ldots,n$ 中每个整数都至少出现一次。

对于每个 $k=1,2,\ldots,n+1$，求该序列长度为 $k$ 的不同子序列数量，并对 $10^9+7$ 取模。

如果两个子序列的内容完全相同，即使它们选取的原序列位置不同，也只计为一种。子序列不要求连续，但必须保持元素的相对顺序。

输入格式

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

输出格式

输出 $n+1$ 行。第 $k$ 行输出长度为 $k$ 的不同子序列数量对 $10^9+7$ 取模后的结果。

样例输入 1

3
1 2 1 3

样例输出 1

3
5
4
1

样例输入 2

1
1 1

样例输出 2

1
1

样例输入 3

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

样例输出 3

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\le n\le10^5$；
• $1\le a_i\le n$；
• $1,2,\ldots,n$ 中每个整数都在序列中出现；
• 所有输入均为整数。