P6725 [COCI 2015/2016 #5] PERICA

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

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

#### 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](https://hsin.hr/coci/archive/2015_2016/) [CONTEST #5](https://hsin.hr/coci/archive/2015_2016/contest5_tasks.pdf) *T3 PERICA***。 Translated by ChatGPT 5