题目描述

给定一个整数数组 A ，考虑 A 的所有非空子序列。
对于任意序列 S ，设 S 的宽度是 S 的最大元素和最小元素的差。
返回 A 的所有子序列的宽度之和。
由于答案可能非常大，请返回答案模 10^9+7。

输入格式

一行，空格隔开，输入整个数组A。

输出格式

一行，输出 A 的所有子序列的宽度之和。

样例数据

input

2 1 3

output

6

解释

子序列为 [1]，[2]，[3]，[2,1]，[2,3]，[1,3]，[2,1,3] 。
相应的宽度是 0，0，0，1，1，2，2 。
这些宽度之和是 6 。

提示

1 <= A.length <= 20000
1 <= A[i] <= 20000