AT_arc077_b [ABC066D] 11

[problemUrl]: https://atcoder.jp/contests/abc066/tasks/arc077_b $ 1,...,n $ の $ n $ 個の整数からなる長さ $ n+1 $ の数列 $ a_1,a_2,...,a_{n+1} $ が与えられます。 この数列には $ 1,...,n $ のどの整数もかならず $ 1 $ 回以上出現することが分かっています。 $ k=1,...,n+1 $ のそれぞれについて、与えられた数列の長さ $ k $ の（連続とは限らない）部分列の個数を求め、 $ 10^9+7 $ で割ったあまりを出力して下さい。

入力は以下の形式で標準入力から与えられる。 > $ n $ $ a_1 $ $ a_2 $ ... $ a_{n+1} $

答えを $ n+1 $ 行に出力せよ。 $ k $ 行目には、長さ $ k $ の部分列の個数を $ 10^9+7 $ で割ったあまりを出力せよ。

### 注意 - $ 2 $ つの部分列が数列として同じであれば、元の数列での位置が異なっていたとしても、$ 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,...,n $ のどの整数も必ず数列に出現する。 - $ n,a_i $ は整数である。 ### Sample Explanation 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 $ の $ 1 $ 通りです。 ### Sample Explanation 2 長さ $ 1 $ の部分列は $ 1 $ の $ 1 $ 通りです。 長さ $ 2 $ の部分列は $ 1,1 $ の $ 1 $ 通りです。 ### Sample Explanation 3 $ 10^9+7 $ で割ったあまりを出力することに注意して下さい。