给定一个序列 $a = (a_{1}, a_{2}, ..., a_{n})$，我们寻找其“变动子序列”。子序列是通过从原序列中删除任意数量（可能为 0）的项得到的。更正式地说，序列 $a$ 的一个子序列是任意序列 $(a_{i_{1}}, a_{i_{2}}, ..., a_{i_{k}})$，其中 $1 \le i_{1} < i_{2} < ... < i_{k} \le n$。变动子序列是指满足任意两个相邻项均不相同的子序列。例如，序列 $(1, 3, 1, 2)$ 是序列 $(1, 2, 3, 1, 3, 2, 2)$ 的一个变动子序列。

我们希望知道给定序列中有多少个不同的非空变动子序列。如果两个子序列在原序列 $a$ 中对应的位置集合不同，则认为它们是不同的。例如，序列 $(1, 2, 3, 1, 3, 2, 2)$ 包含两个形式为 $(1, 3, 1, 2)$ 的不同变动子序列。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 500\,000$)，表示序列 $a$ 的长度。第二行包含 $n$ 个整数 $a_{i}$ ($1 \le a_{i} \le 500\,000$)。

输出格式

程序应在标准输出的第一行输出一个整数：输入序列中非空变动子序列的数量，结果对 $10^{9} + 7$ 取模。

样例

输入 1

4
1 2 1 1

输出 1

9

说明

序列 $(1, 2, 1, 1)$ 的变动子序列包括：

• $(1)$ - 计数三次，
• $(2)$ - 计数一次，
• $(1, 2)$ - 计数一次，
• $(2, 1)$ - 计数两次，
• $(1, 2, 1)$ - 计数两次。