Background

黄老板拥有众多的MZ，具体来说一共有n个，上至$2^{31}-1$年女鬼，此大年也，下至1年顽童，此小年也。黄老板一共可以活n 天（好像发现什么不得了的东西），现在黄老板定义了自己在人生的第k天的开心值为在所有MZ中取出k个的每种方案年纪最小的，现在黄老板想知道自己的人生的第k天到底有多快乐，因为黄老板日理一机，所以黄老板找到了他的顾问，来帮忙解决这个问题，顾问当然知道怎么做，但是他想用这个问题来考考应聘的你。

Description

组合数$\binom{n}{m}$表示从 $n$ 个元素中取出 $m$ 个的方案数。
给定$n$,$k$，再输入$n$个数， 求：从这$n$个数中任意取出$k$个的$\binom{n}{k}$种方案中，每种方案中被取的数的最小值的和。
答案可能很大，对$10^9+7$取模。

Format

Input

输入的第1行包含两个数$n,k$，意义如上。
接下来n行包含$n$个整数，每个数均为不超过$10^9$的⾮负整数。

Output

输出一个整数，表示答案。

Sample 1

Input

5 2
1 2 3 4 5

Output

20

Limitation

共有 $10$个测试点：
$40\%$ 的数据，$n \le 1 \times 10^3$
$80\%$ 的数据，$n \le 5 \times 10^4$
$100\%$的数据，$n \le 2 \times 10^5$

猴急（Afterword）

你算出来的值让黄老板很高兴，于是受性大发，最后受性大发的黄老板吓跑了所有的MZ。因为这个你和顾问都被送上了法庭。