小P非常喜爱军事，今天他要指挥一场战斗:
有n+1个士兵，其中每一个兵属于第S_i个兵种(S_i≤n)，每个兵种至少有一个兵 (即只有一个兵种有两个兵)
现在小P从前到后检阅每个兵，在检阅每一个兵时，他都可以选择是否把这个兵加入当前作战队列的队尾。
对于长度为L的作战队列，问有多少种组合方式(如果两个队列中相同位置兵种相同，则只算一种) ,结果对10⁹+7取模 

第一行一个正整数n，表示有n种兵种。
第二行n+1个正整数S1……Sn+1，描述每个士兵的兵种。

n+1行，对于第 i 行，输出一个整数表示可组成长度为 i 的不同队列的数量，答案对10⁹+7取模。

样例解释
长度为1的作战队列有3个：1，2，3。
长度为2的作战队列有5个：11，12，13，21，23。
长度为3的作战队列有4个：121，123，113，213。
长度为4的作战队列有1个：1213。


对于20%的数据，n≤20。
对于40%的数据，n≤2000。
对于100%的数据，n≤100000，1≤ai≤n。