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。因为这个你和顾问都被送上了法庭。