레이팅 미적용설명
- “I’m stopping by Žnidaršić’s house, you play the piano, Perica.”
- ”Ok, dad, I will!”
And so, Perica began playing the piano. His piano consists of \(N\) keys. Each key has a value written
on it, \(a_{i}\). 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.
제약
In test cases worth 40% of total points, it will additionally hold 1 ⩽\(N\) ⩽1000.
입력 형식
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 \(a_{i}\) (0 ⩽\(a_{ij}\) ⩽\(10^{9}\)).
출력 형식
The first and only line of output must contain the required number from the task.
예제 1
입력
5 3
2 4 2 3 4
5 1
1 0 1 1 1
5 2
3 3 4 0 0출력
output
output
39
4
31
Pojašnjenje prvog primjera: 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].문제 정보