Description

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

Please compute the sum of the maximum value over all combinations of $K$ numbers, modulo $10^9 + 7$.

Input Format

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

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

Output Format

Output one integer on one line: the sum of the maximum value over all combinations of $K$ numbers, modulo $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

Hint

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

Constraints

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

Notes

Translated from COCI2015-2016 CONTEST #5 T3 PERICA。

Translated by ChatGPT 5