分数: 700 点
问题陈述
有 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