Problem Description

Given a sequence of length $N$, denoted as $a_1, a_2, \dots, a_N$.

You are required to find the sum of the maximum numbers in all combinations of $K$ numbers, modulo $10^9+7$.

Input Format

The first line contains two integers $N$ and $K$.

The second line contains a sequence of length $N$, denoted as $a_1, a_2, \dots, a_N$.

Output Format

Output a single integer, which is the sum of the maximum numbers in all combinations of $K$ numbers, modulo $10^9+7$.

Sample Input and Output

Sample Input #1

5 3
2 4 2 3 4

Sample Output #1

39

Sample Input #2

5 1
1 0 1 1 1

Sample Output #2

4

Sample Input #3

5 2
3 3 4 0 0

Sample Output #3

31

Notes

Sample Explanation

Sample 1

All combinations of $K$ numbers are: $[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]$.

Data Size and Constraints

For $40\%$ of the data, $N \le 10^3$;
For $100\%$ of the data, $1 \le N \le 10^5$, $1 \le K \le 50$.

Notes

This problem is translated from COCI2015-2016 CONTEST #5 T3 PERICA.

见题面 Input 部分

见题面 Output 部分