Description

Xiao Ben is obsessed with multiplication. His favorite thing to do is: from a multiset with $n$ elements, choose $k$ numbers, and use the product of these $k$ numbers as the score of this combination.

Xiao Ben wants to try all such combinations, and then compute the sum of the scores of all combinations. However, he still needs to crush us rookies in a mock contest, so he has to hand this task over to you.

As a “not so kind” problem setter, you also need to take the answer modulo $10^9 + 7$.

Input Format

The first line contains two positive integers $n,k$.
The second line contains $n$ positive integers $a_i$, representing the elements in the multiset.

Output Format

Output one line with one integer representing the answer.

3 3
1 1 1

1

4 3
1 1 1 2

7

10 7
11 45 14 19 19 8 10 8 17 23

693404716

Hint

[Explanation for Sample 2]
There are four ways to choose: one is $\{1,1,1\}$, and the other three are all $\{1,1,2\}$. The sum of the scores is $7$.

[Constraints]
For $100\%$ of the testdata, $1\le k \le n \le 1.2\times 10^5$, $1\le a_i \le 10^8$。

Translated by ChatGPT 5