题目描述

有 $N$ 个石头排成一列，从左到右第 $i$ 个石头被涂上了颜色 $C_i$。

すぬけ君可以进行如下操作，任意次数（可以为 $0$ 次）：

• 选择两个被涂成相同颜色的石头，将它们之间所有石头的颜色都改为这两块石头的颜色。

请你求出，最终可能得到的石头颜色序列有多少种，将答案对 $10^9+7$ 取模。

输入格式

输入以如下格式从标准输入读入。

$N$ $C_1$ $C_2$ $\cdots$ $C_N$

输出格式

输出最终可能得到的石头颜色序列的种数，对 $10^9+7$ 取模。

样例 1

输入

5
1
2
1
2
2

输出

3

样例 2

输入

6
4
2
5
4
2
4

输出

5

样例 3

输入

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)$
• 输入均为整数

样例解释 1

可以得到以下 $3$ 种石头颜色序列。

• 不进行操作，得到 $(1,2,1,2,2)$
• 选择第 $1$、$3$ 个石头进行操作，得到 $(1,1,1,2,2)$
• 选择第 $2$、$4$ 个石头进行操作，得到 $(1,2,2,2,2)$

由 ChatGPT 4.1 翻译