题目描述

庭院中的能量送入长廊，彩灯沿着林间小径次第亮起，每种颜色都有一个正整数编号。大笨龙将自己偏爱的颜色挂了许多遍，盼着这段灯景能得到聪明兔的赞许。聪明兔提议，为长廊的每一段灯景评定价值，作为舞会开场前的最后一项小竞赛。

彩灯的颜色编号构成一个长度为 $n$ 的正整数序列 $A_1, A_2, \ldots, A_n$。

对于任意满足 $1 \le l \le r \le n$ 的区间 $[l, r]$，令

$S(l, r) = \{A_l, A_{l+1}, \ldots, A_r\}$。

这里的 $S(l, r)$ 是一个集合，相同的整数只保留一次。定义

$f(l, r) = |S(l, r)|, \quad g(l, r) = \sum_{x \in S(l,r)} x,$

即 $f(l, r)$ 为区间内不同整数的个数，$g(l, r)$ 为这些不同整数的数值之和。区间 $[l, r]$ 的价值为

$V(l, r) = f(l, r)^2 \times g(l, r)$。

请你求出所有非空连续子区间的价值之和，即

$\sum_{l=1}^n \sum_{r=l}^n f(l, r)^2 g(l, r)$。

由于答案可能很大，请输出答案对 $10^9 + 7$ 取模后的结果。

输入格式

从文件 colors.in 中读入数据。

第一行包含一个正整数 $n$，表示序列的长度。

第二行包含 $n$ 个正整数 $A_1, A_2, \ldots, A_n$，相邻两个整数之间用一个空格隔开。

输出格式

输出到文件 colors.out 中。

输出一行一个非负整数，表示所有非空连续子区间的价值之和对 $10^9 + 7$ 取模后的结果。

样例 1

4
2 1 3 2

218

样例1解释

对于区间 $[1, 3]$，不同整数构成的集合为 $S(1, 3) = \{1, 2, 3\}$，因此 $f(1, 3) = 3$，$g(1, 3) = 6$，该区间的价值为 $3^2 \times 6 = 54$。

对于区间 $[1, 4]$，虽然整数 $2$ 出现了两次，但它只计算一次，因此 $S(1, 4) = \{1, 2, 3\}$，该区间的价值也为 $54$。

所有非空连续子区间的价值之和为 $218$。

样例 2

3
1 1 1

6

样例2解释

任意非空连续子区间内都只有整数 $1$，所以每个区间的价值均为 $1$。一共有 $6$ 个非空连续子区间，答案为 $6$。

样例 3

3
1 2 1

40

样例3解释

三个长度为 $1$ 的区间价值之和为 $1 + 2 + 1 = 4$。两个长度为 $2$ 的区间价值均为 $2^2 \times (1 + 2) = 12$，长度为 $3$ 的区间价值也为 $12$。总和为 $4 + 12 + 12 + 12 = 40$。

样例4

见附件中的 colors4.in 与 colors4.ans。

数据范围

对于所有数据，$1 \le n \le 5 \times 10^5$，$1 \le A_i \le 2 \times 10^9$。

同一个整数在同一个区间中无论出现多少次，在计算 $f(l, r)$ 和 $g(l, r)$ 时均只计算一次。

本题共有 $25$ 个测试点，每个测试点 $4$ 分。

测试点编号	$n \le$	$A_i \le$	特殊性质
$1 \sim 2$	$10$	$2 \times 10^9$	无
$3 \sim 6$	$300$
$7 \sim 10$	$3000$
$11 \sim 14$	$10^5$	$10$
$15 \sim 16$	$5 \times 10^5$	$2 \times 10^9$	A
$17 \sim 18$			B
$19 \sim 21$	$10^5$		无
$22 \sim 25$	$5 \times 10^5$

特殊性质 A：所有 $A_i$ 均相等。

特殊性质 B：所有 $A_i$ 两两不同。

样例附件

下载全部样例（colors-samples.zip）