← 返回题目列表

AtCoder · agc031_b

B. 黑白棋

中文机器翻译题面 查看原题

分数: 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