问题 DG: 子序列的极差和
内存限制：128 MB
时间限制：3.000 S
评测方式：文本比较
命题人：
提交：79
解决：17
题目描述
我们知道，对于一个序列，它的极差是序列中的最大值减去最小值。
同时我们知道，一个序列的子序列是由它本身删去若干个元素得到的。
现在给一个长度为 $n$ 的序列，你需要求出其所有长度为 $k$ 的子序列的极差之和。
（由于这个答案很大，所以你输出的结果需要对 $10^9+7$ 取模）
同时我们知道，一个序列的子序列是由它本身删去若干个元素得到的。
现在给一个长度为 $n$ 的序列，你需要求出其所有长度为 $k$ 的子序列的极差之和。
（由于这个答案很大，所以你输出的结果需要对 $10^9+7$ 取模）
输入
第一行，输入两个整数，$n,k$ ($1 \leq k \leq n \leq 10^5$)
第二行，输入 $n$ 个整数 $a_i$ ,代表这个序列 ($|a_i| \leq 10^9$)
第二行，输入 $n$ 个整数 $a_i$ ,代表这个序列 ($|a_i| \leq 10^9$)
输出
输出其所有长度为 $k$ 的子序列的极差之和对$10^9+7$ 取模的结果
样例输入 复制
4 2
1 1 3 4
样例输出 复制
11
提示
长度为2的子序列共有6个，分别是$ \{1,1\},\{1,3\},\{1,4\},\{1,3\},\{1,4\}, \{3,4\}$，它们的极差和是11