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

描述

给你一个长度为 \(n\) 的序列\(a[1..n]\)，定义这个序列的子序列为由这个序列删掉若干个元素并将剩下的元素按顺序连接组成的序列，定义一个序列的值为这个序列的最大数减去最小数，求这个序列的所有

子序列的值的和 \(\mod 1000000007\)。

输入格式

第一行一个数，\(n\) 。

第二行 \(n\) 个数，第i个数表示\(a[i]\)

输出格式

输出一个数表示答案。

输入样例

5
2 5 4 1 3

输出样例

72

数据范围及特点

对于\(30\%\)的数据，\(n \leq 20\)

对于\(60\%\)的数据，\(n \leq 1000\)

对于\(100\%\)的数据，\(1\leq n\leq 200000\)，\(0 \leq a[i] \leq 10^9\)