序列计数(count)

题目描述

长度为$n+1$的序列$A$，其中的每个数都是不大于$n$的正整数，且$n$以内每个正整数至少出现一次。

对于每一个正整数$k=1,..,n+1$，求出的本质不同的长度为$k$的子序列(不一定要连续)的数量。对$10^9+7$取模。

输入格式

第一行一个正整数$n$。

第二行$n+1$个正整数$A_{1}..A_{n+1}$，描述序列$A$。

输出格式

$n+1$行，对于第$i$行，输出一个整数表示长度为$i$的本质不同子序列的数量，对$10^9+7$取模。

样例

input1

3
1 2 1 3

output1

3
5
4
1

explanation

长度为$1$的子序列有$3$个：$1$ ，$2$ ，$3$。

长度为$2$的子序列有$5$个：$11$ ，$12$ ，$13$，$21$，$23$。

长度为$3$的子序列有$4$个：$121$ ，$123$ ，$113$，$213$。

长度为$4$的子序列有$1$个：$1213$。

input2

见样例 ex_count2.in。

output2

见样例 ex_count2.out。

数据范围和约定

对于$20\%$的数据，$n\le20$。

对于$40\%$的数据，$n\le2000$。

对于额外$20\%$的数据，保证$A$中相同的数一定相邻。

对于$100\%​$的数据，$n\le100000​$，$1\le A_{i}\le n​$。

时间限制：$1s$ 空间限制：$512MB$

样例下载

样例下载