Description

在数轴上有 $n$ 个点，它们的坐标分别为 $(1,0)$ , $(2,0)$, $\cdots$ , $(n,0)$.每个点都有一个颜色，坐标为 $(i,0)$ 的点颜色为 $A_i$ .

$A$ 君在所有颜色相同的点对间都画上了圆弧。更具体地，若有 $A_i = A_j$ 且 $i \geq j$，那么 $A$ 君会画一条圆弧连接$(i, 0)$ 与 $(j, 0)$ ，且这条弧颜色为 $A_i$ ，圆心在 $X$ 轴上，所有的圆弧都在第一象限内。

现在 $A$ 君想知道，有多少对不同颜色的圆弧相交了。请你告诉他答案模 $10^9 + 7$ 后的值。

Input Format

第一行一个整数 $n$ 表示点数。

第二行 $n$ 个整数 $A_i$ 表示所有点的颜色。

Output Format

仅一行一个整数表示答案。

Sample

样例输入

8
1 2 3 1 2 3 2 1

样例输出

8

Hint

$20\%$的数据： $n \leq 10$

$40\%$的数据： $n \leq 1000$

另有 $30\%$ 的数据：每种颜色的点数不超过 $20$

$100\%$的数据： $1 \leq n,Ai \leq 10^5$