题目描述

给定一个长度为 $N$ 的序列 $a_1,a_2,\dots,a_N$。

请你求出所有 $K$ 个数的组合中最大数之和 $\bmod\ 10^9+7$ 的结果。

输入格式

输入第一行两个整数 $N,K$。

第二行一个长度为 $N$ 的序列 $a_1,a_2,\dots, a_N$。

输出格式

输出一行一个整数，为所有 $K$ 个数的组合中最大数之和 $\bmod\ 10^9+7$ 的结果。

5 3
2 4 2 3 4

39

5 1
1 0 1 1 1

4

5 2
3 3 4 0 0

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]$。

数据规模与约定

对于 $40\%$ 的数据，$N\le 10^3$；
对于 $100\%$ 的数据，$1\le N\le 10^5$，$1\le K\le 50$。

说明

题目译自 COCI2015-2016 CONTEST #5 T3 PERICA。