You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

问题描述

数列A中有n个整数。

f(S) 表示数列S中的最大值减去最小值。

如f({1,3,8}) = 8 - 1 = 7

f({2,4,7,3} = 7 - 2 = 5。

求 A 的 所有 大小为 k 的子数列S 的 f(S) 之和 mod 1e9+7。

输入格式

第一行 n, k。

第二行 n 个数，表示集合 A。

输出格式

一个整数。

4 2
1 1 3 4

11

大小为2的子数列有 1 1, 1 3, 1 4, 1 3, 1 4, 3 4。 f值分别为 0， 2， 3， 2， 3， 1， 和为 11。

6 3
10 10 10 -10 -10 -10

360

数据范围

$1 \le n, k \le 10^5$

$1\le |a_i| \le 10^9$