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, $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$.

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

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

Sample Input 1 | Sample Output 1 |
---|---|

5 3 2 4 2 3 4 |
39 |

Sample Input 2 | Sample Output 2 |
---|---|

5 1 1 0 1 1 1 |
4 |

Sample Input 3 | Sample Output 3 |
---|---|

5 2 3 3 4 0 0 |
31 |