COCI '15 Contest 5 #3 Perica

Points: 10 (partial)

Time limit: 0.6s

Haskell 0.75s

Memory limit: 64M

Problem types

"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$ ~N~ keys. Each key has a value written on it, $a_i$ ~a_i~. When Perica plays the piano, he presses exactly $K$ ~K~ different keys at the same time. The piano is a bit strange because, after pressing $K$ ~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$ ~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$ ~1\,000\,000\,007~.

Input

The first line of input contains two integers $N$ ~N~ and $K$ ~K~ $(1 \le N \le 100\,000, 1 \le K \le 50)$ . The following line of input contains $N$ ~N~ integers $a_i$ ~a_i~ $(0 \le a_i \le 10^9)$ ~(0 \le a_i \le 10^9)~.

Output

The first and only line of output must contain the required number from the task.

Scoring

In test cases worth 40% of total points, it will additionally hold $1 \le N \le 1\,000$ ~1 \le N \le 1\,000~.

Sample Input 1

5 3
2 4 2 3 4

Sample Output 1

Explanation for Sample Output 1

All selections of $K$ ~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].

Sample Input 2

5 1
1 0 1 1 1

Sample Output 2

Sample Input 3

5 2
3 3 4 0 0

Sample Output 3

Comments

-9

Plasmatic commented on April 16, 2019, 3:37 a.m. ← edited →

this is not dp

edit: :O apparently there is a dp-like solution

This comment is hidden due to too much negative feedback. Show it anyway.