暂无测试数据。

给定一个长度为\(n\)的序列\(A\)。
定义\[f(l,r)=max( a_l,a_{l+1},....,a_r)\]
\[g(l,r)=min(a_l,a_{l+1},....,a_r)\]
希望你求出：

\[(\sum_{l=1}^{n} \sum_{r=1}^{n} f(l,r) \times g(l,r)) mod (10^9+7)\]

输入格式

首先输入n。
接下来输入n个数，描述序列 A。

输出格式

输出一行一个整数代表答案。

输入输出样例

输入

4
1 2 3 4

输出

65

PS

对于100%的数据，n<=500000,0<=A[i]<=10^9。