A1315 | [COCI-2015_2016-contest5]#3 PERICA

- “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, 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 00
7.

The first line of input contains two integers N and K (1 6 N 6 100 000, 1 6 K 6 50).
The following line of input contains N integers ai (0 6 aij 6 109 ).

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