Background

On the magical land of Xiaoben, there is an infamous coach Xiaoben.

Solution write-up: https://blog.csdn.net/kkkksc03/article/details/84928333.

Problem Description

Xiaoben loves multiplication. His favorite thing to do is: choose $K$ numbers from a sequence with $N$ elements (note: you cannot choose the same element multiple times, but choosing different elements with the same value is allowed), and then take the product of these $K$ numbers as the score of this combination.

Xiaoben wants to try all such combinations and compute the sum of the scores of all combinations. But he also needs to run a mock contest to crush us newbies, so he has to hand this task to you.

Xiaoben (in some ways) is still very kind, so you do not need to use big integers. You only need to output the answer modulo $10^9+7$.

Input Format

The first line contains two integers $N$ and $K$.

The second line contains $N$ integers $A_i$ describing the sequence.

Output Format

Output one integer in one line, representing the answer.

3 3
1 1 1

1

4 3
1 1 1 2

7

Hint

Explanation for Sample #2:

Xiaoben can choose four combinations: {A[1],A[2],A[3]},{A[1],A[2],A[4]},{A[1],A[3],A[4]},{A[2],A[3],A[4]}. Their scores are $1,2,2,2$ respectively. The total is $7$.

Constraints:

For $10\%$ of the testdata, $N\le 5000, K\le 2$.

For $30\%$ of the testdata, $N\le 10^5, K\le 3$.

For $50\%$ of the testdata, $N\le 10^5, K\le 5$.

For $100\%$ of the testdata, $1\le N\le 10^5, 1\le K \le 300 \& \& K\le N, 1\le A[i]\le 10^8$.

Translated by ChatGPT 5