問題文

長さ $N$ の配列 $a$ が与えられます。$\\$ $1 \leq l \leq r \leq N$ について、$f(l, r)$ を以下のように定義します。

• $a_l, a_{l+1}, ..., a_r$ が全て異なる場合、$f(l, r) = \displaystyle \sum_{l \leq i \leq r} a_i$
• そうでない場合、$f(l, r) = 0$

$\displaystyle \sum_{1 \leq l \leq r \leq N} f(l, r)$ を求めてください。 ただし、答えは非常に大きくなる可能性があるので、$10 ^ 9 + 7$ で割った余りを出力してください。

制約

• $1 \leq N \leq 10 ^ 5$
• $1 \leq a_i \leq 10 ^ 9$

入力

入力はすべて整数である。

N
a1 a2 ... aN

出力

計算結果を一行に出力せよ。

サンプル

3
1 2 3

20

$a$ に含まれる数値はすべて異なるので、答えは $(1) + (2) + (3) + (1 + 2) + (2 + 3) + (1 + 2 + 3) = 20$ です。

3
1 1 1

3

10
31415 9 265358 9 7 9 323846264 338327 9 5028841

615013335

$10 ^ 9 + 7$ で割った余りを出力することに注意してください。