Migrated from Lutece 2523 我，不是说了能力要平均值么 · 改三

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

转生异世界时，栗原海里请求神赐予她平均值的能力，导演组故意找了一个不会计算平均数的神，神很自然地给出了最大值与最小值和的一半的结果——在数学上这显然是错误的，但是剧情就变得很有意思了。

异世界共有 $n$ 个生物，分别编号为 $1\ldots n$。神会以均匀随机的方式选择一个区间 $[l,r]\ (1\le l\le r\le n,l,r\in \mathbb{N}_+)$，并取编号在区间内的所有生物的能力「平均值」作为栗原海里的能力值。栗原海里想知道，如果用神自己对平均值的定义的话（也就是将区间内生物能力值的最大值与最小值和的一半作为栗原海里的能力值），自己的能力值的期望有多大。

Input

第一行一个整数 $n$，表示异世界生物数。

第二行 $n$ 个正整数 $a_i$，第 $i$ 个数表示第 $i$ 个生物的能力值。

Output

输出一行一个整数，表示所求期望对 $10^9+7$ 取模后的值。

这个期望一定是有理数，对于一个表示成 $\frac{p}{q}$ 的有理数（其中 $p\in \mathbb{N},q\in \mathbb{N}_+$，且 $\gcd(p,q)=1$），请输出 $p\times q^{-1}$ 对 $10^9+7$ 取模后的值，其中 $q^{-1}$ 表示 $q$ 在模 $10^9+7$ 意义下的逆元。

Samples

6
1 1 4 5 1 4

809523818

Constraints

$1\le n\le 10^6,1\le a_i\le 10^9$

Note

样例输出的分数形式为 $\frac{59}{21}$。

Resources

2021 UESTC ICPC Training for Data Structures