문제

1 second, 64 MB, 100 points - “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 007.

입력

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 ai (0 ⩽aij ⩽109).

출력

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

예제 입력 1

5 3
2 4 2 3 4

예제 출력 1

39

예제 입력 2

5 1
1 0 1 1 1

예제 출력 2

4

예제 입력 3

5 2
3 3 4 0 0

예제 출력 3

31