描述

给你一个长度为 \(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\)