Description

小A给你N个整数.第i个整数是ai。你现在可以对这个N个整数进行任意 次操作（也可以不操作)。

每次操作中，可以选择两个相同的数字，并且把这两个数字之间的数字全部都 变为所选择的数字

例如在序列[1，2, 3, 2]中，选择这两个2进行操作，之后序列会变为[1，2, 2, 2]。 即把中间的3变成了 2。

现在小A想知道所有可能得到的序列有多少个。

答案模10^9 + 7。

Input Format

第1行输入一个整数N

接下来有N行，每行输入一个数字，分别代表ai aN

Output Format

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

Sample

样例输入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

Hint

1 =< N <= 2 x 10^5

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

•所有输入的值都是整数