该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

给定一个长度为n的序列A。定义f(l,r)=max⁡(a_l,a_(l+1),…,a_r ),g(l,r)=min⁡(a_l,a_(l+1),…,a_r)，希望你求出： (∑(l=1)^n▒∑(r=l)^n▒〖f(l,r)×g(l,r) 〗)mod (〖10〗^9+7)(具体见PDF文件)

Input Format

输入文件名为seq.in。 首先输入n。 接下来输入n个数，描述序列A。

Output Format

输出文件名为seq.out。 输出一行一个整数代表答案。

Sample

【输入样例】

7
0 35 40 45 56 65 94

【输出样例】

66636

Hint

对于30%的数据，n≤5000;

对于60%的数据，n≤50000;

对于100%的数据，n≤500000,0≤A[i]≤〖10〗^9