시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 64 MB | 224 | 89 | 77 | 41.176% |
And so, Perica began playing the piano. His piano consists of N keys. Each key has a value written on it, ai. When Perica plays the piano, he presses exactly K different keys at the same time. The piano is a bit strange because, after pressing K keys at the same time, it will play only the key with the largest value. Perica is going to play each combination of K keys on the piano and he wants to know the sum of values of the keys that will be played.
Help Perica determine the remainder of that number modulo 1 000 000 007.
The first line of input contains two integers N and K (1 ≤ N ≤ 100 000, 1 ≤ K ≤ 50).
The following line of input contains N integers ai (0 ≤ ai ≤ 109).
The first and only line of output must contain the required number from the task.
5 3 2 4 2 3 4
39
5 1 1 0 1 1 1
4
5 2 3 3 4 0 0
31
All selections of K keys 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].