COCI '15 Contest 5 #3 Perica

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 0.6s
Haskell 0.75s
Memory limit: 64M

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

"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.

Input

The first line of input contains two integers N and K (1 \le N \le 100\,000, 1 \le K \le 50). The following line of input contains N integers a_i (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.

Sample Input 1

5 3
2 4 2 3 4

Sample Output 1

39

Explanation for Sample Output 1

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].

Sample Input 2

5 1
1 0 1 1 1

Sample Output 2

4

Sample Input 3

5 2
3 3 4 0 0

Sample Output 3

31

Comments


  • -10
    Plasmatic  commented on April 15, 2019, 11:37 p.m. edited

    This comment is hidden due to too much negative feedback. Click here to view it.