题目描述

$N$ 個の石が一列に並んでいて、左から $i$ 個目の石は色 $C_i$ で塗られています。

すぬけ君は、以下の操作を $0$ 回以上の任意の回数行います。

• 同じ色で塗られている $2$ つの石を選ぶ。それらの石の間に置かれている石をすべて、選んだ石と同じ色で塗りかえる。

最終的な石の色の列としてありうるものの個数を $10^9+7$ で割ったあまりを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $C_1$ $:$ $C_N$

输出格式

最終的な石の色の列としてありうるものの個数を $10^9+7$ で割ったあまりを出力せよ。

题目大意

有 $N$ 块石头摆成一行，从左数第 $i$ 块石头的颜色是 $C_i$。

现在すぬけ会进行 $0$ 次或若干次如下操作：选取两块颜色相同的石头并将两块石头之间的所有石头都染成与这两块石头相同的颜色。

求最终所有可能的石头排列方案数，答案对 $10^9 + 7$ 取模。

5
1
2
1
2
2

3

6
4
2
5
4
2
4

5

7
1
3
1
2
3
3
2

5

提示

制約

• $1\ \leq\ N\ \leq\ 2\times\ 10^5$
• $ 1\ \leq\ C_i\ \leq\ 2\times\ 10^5(1\leq\ i\leq\ N) $
• 入力はすべて整数である

Sample Explanation 1

以下の $3$ 通りの石の色の列を作ることができます。 - 操作を行わないことで、$(1,2,1,2,2)$ - $1,3$ 番目の石を選んで操作を行うことで、$(1,1,1,2,2)$ - $2,4$ 番目の石を選んで操作を行うことで、$(1,2,2,2,2)$