问题描述

有 $N$ 个石头排成一行。从左边数第 $i$ 个石头的颜色为 $C_i$。

Snuke 将执行以下操作零次或多次：

• 选择两个相同颜色的石头。将它们之间的所有石头重新涂上这两个石头的颜色。

计算可能的最终石头颜色序列的数量，对 $10^9+7$ 取模。

约束条件

• $1 \leq N \leq 2\times 10^5$
• $1 \leq C_i \leq 2\times 10^5 (1\leq i\leq N)$
• 输入中的所有值都是整数。

输入

输入通过标准输入给出，格式如下:

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

输出

打印可能的最终石头颜色序列的数量，对 $10^9+7$ 取模。

示例输入 1

5
1
2
1
2
2

示例输出 1

3

我们可以得到三种石头颜色序列，如下所示：

• $(1,2,1,2,2)$，什么也不做。
• $(1,1,1,2,2)$，选择第一和第三个石头执行操作。
• $(1,2,2,2,2)$，选择第二和第四个石头执行操作。

示例输入 2

6
4
2
5
4
2
4

示例输出 2

5

示例输入 3

7
1
3
1
2
3
3
2

示例输出 3

5