Sum of Maximum Elements in K-Combination

Given a sequence of length \(N\) denoted as \(a_1, a_2, \dots, a_N\) and an integer \(K\), your task is to compute the sum of the maximum elements among all combinations of \(K\) numbers selected from the sequence. Formally, for every combination of \(K\) elements, find its maximum element and sum up all these maximums. Finally, output the result modulo \(10^9+7\).

The problem can be reformulated as follows: Sort the sequence \(a_1, a_2, \dots, a_N\) in non-decreasing order. For each element \(a_i\) (with \(i\ge K\)), it becomes the maximum in \(C(i-1, K-1)\) combinations (choosing \(K-1\) elements from the first \(i-1\) numbers). Thus, the answer is computed as:

[ \text{Answer} = \sum_{i=K}^{N} a_{(i)} \times \binom{i-1}{K-1} \mod (10^9+7), ]

where \(a_{(i)}\) is the \(i\)-th smallest element of the sequence.

inputFormat

The first line contains two integers \(N\) and \(K\) (the length of the sequence and the number of elements to choose respectively).

The second line contains \(N\) space-separated integers \(a_1, a_2, \dots, a_N\), representing the sequence.

outputFormat

Output a single integer, the sum of the maximum elements among all \(K\)-combinations, taken modulo \(10^9+7\).

sample

3 2
1 2 3

8