Description

小A给你 $N$ 个整数，第 $i$ 个整数是 $a_i$ 。你现在可以对这 $N$ 个整数进行任意次操作（也可以不操作）。 每次操作中，可以选择两上个相同的数字，并且把这两个数字之间的数字全部变为所选择的数字，例如在序列[1，2，3，2]中，选择这两个2进行操作，之后序列会变为[1，2，2，2]。即把中间的3变成了2。 现在小A想知道所有可能得到的序列有多少个？。 答案模$10^9+7$。

Format

Input

第1行输入一个整数 $N$ 接下有 $N$ 行，每行输入一个数字，分别代表 $a_1~a_N$

Output

输出一个数，表示所有可能的序列的个数。（模 $10^9+7$ ）

Samples

5
1
2
1
2
2

3

样例解释：

一共有三种可能的序列：

[1,2,1,2,2] (什么都不做)

[1,1,1,2,2] (选择前两个1)

[1,2,2,2,2] (选择前两个2)

6
4
2
5
4
2
4

5

7
1
3
1
2
3
3
2

5

Limitation

1=<N<=2*10^5

1=<ai<=2*10^5 (1=<i<=N)

所有输入的值都是整数。