题目描述

给定一个由 $1, \ldots, n$ 这 $n$ 个整数构成，长度为 $n+1$ 的数列 $a_1, a_2, \ldots, a_{n+1}$。已知在这个数列中，$1, \ldots, n$ 的每个整数都至少出现过一次。

对于 $k=1, \ldots, n+1$ 的每一个 $k$，求出长度为 $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

输出

3
5
4
1

样例 2

输入

1
1 1

输出

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

输出

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

说明/提示

注意

• 如果两个子序列作为数列完全相同，即使它们在原数列中的位置不同，也只计为一种。
• 一个数列 $a$ 的长度为 $k$ 的子序列，是指从 $a$ 的元素中选出 $k$ 个，保持原有顺序排列而成的新数列。例如，数列 $1,2,3,4,5$ 的长度为 $3$ 的子序列有 $1,3,5$、$1,2,3$ 等，而 $3,1,2$ 或 $1,10,100$ 则不是该数列的子序列。

数据范围

• $1 \leq n \leq 10^5$
• $1 \leq a_i \leq n$
• 数列中每个整数 $1,\ldots,n$ 一定都会出现。
• $n, a_i$ 均为整数。

样例解释 1

长度为 $1$ 的子序列有 $1$、$2$、$3$ 共 $3$ 种。 长度为 $2$ 的子序列有 $1,1$、$1,2$、$1,3$、$2,1$、$2,3$ 共 $5$ 种。 长度为 $3$ 的子序列有 $1,1,3$、$1,2,1$、$1,2,3$、$2,1,3$ 共 $4$ 种。 长度为 $4$ 的子序列只有 $1,2,1,3$ 一种。

样例解释 2

长度为 $1$ 的子序列只有 $1$ 一种。 长度为 $2$ 的子序列只有 $1,1$ 一种。

样例解释 3

请注意需要对 $10^9+7$ 取模后输出。

由 ChatGPT 5 翻译