“我要顺路去一趟 Žnidaršić 的家，你弹会儿钢琴，Perica。” “好的，爸爸，我会的！”

于是，Perica 开始弹钢琴。他的钢琴有 $N$ 个琴键。每个琴键上都写着一个数值 $a_i$。当 Perica 弹钢琴时，他会同时按下恰好 $K$ 个不同的琴键。这架钢琴有点奇怪，因为在同时按下 $K$ 个琴键后，它只会发出其中数值最大的那个琴键的声音。Perica 打算尝试按下所有可能的 $K$ 个琴键的组合，他想知道所有弹奏出的琴键数值之和。

请帮助 Perica 求出该数值模 $1\,000\,000\,007$ 的余数。

输入格式

第一行包含两个整数 $N$ 和 $K$（$1 \le N \le 100\,000$，$1 \le K \le 50$）。

第二行包含 $N$ 个整数 $a_i$（$0 \le a_i \le 10^9$）。

输出格式

输出的第一行，也是唯一的一行，应包含题目所要求的数值。

子任务

在占总分 40% 的测试数据中，额外满足 $1 \le N \le 1000$。

样例

输入 1

5 3
2 4 2 3 4

输出 1

39

输入 2

5 1
1 0 1 1 1

输出 2

4

输入 3

5 2
3 3 4 0 0

输出 3

31

说明

样例 1 说明：

所有选择 $K$ 个琴键的组合为：$[2, 4, 2]$，$[2, 4, 3]$，$[2, 4, 4]$，$[2, 2, 3]$，$[2, 2, 4]$，$[2, 3, 4]$，$[4, 2, 3]$，$[4, 2, 4]$，$[4, 3, 4]$，$[2, 3, 4]$。