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)$ $(1 \leq N \leq 100 000, 1 \leq K \leq 50)$ . The following line of input contains $N$ $N$ integers $a_i$ $a_{i}$ $(0 \le a_i \le 10^9)$ $(0 \leq a_{i} \leq 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 \leq N \leq 1 000$ .

Sample Input 1

Copy

5 3
2 4 2 3 4

Sample Output 1

Copy

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

Copy

5 1
1 0 1 1 1

Sample Output 2

Copy

Sample Input 3

Copy

5 2
3 3 4 0 0

Sample Output 3

Copy

Comments

-10

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.