Problem Description

Xiao Ben is passionate about multiplication. His favorite activity is to select $k$ numbers from a multiset containing $n$ elements and calculate the product of these $k$ numbers as the score for this combination.

Xiao Ben wants to try all possible combinations and then sum up all the scores of these combinations. However, he is busy organizing simulation contests to overwhelm us, so he has delegated this task to you.

As a not-so-kind problem setter, you are also required to take the answer modulo $10^9 + 7$.

Input Format

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

Output Format

Output a single integer representing the answer.

Sample Input and Output

Sample Input #1

3 3
1 1 1

Sample Output #1

1

Sample Input #2

4 3
1 1 1 2

Sample Output #2

7

Sample Input #3

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

Sample Output #3

693404716

Notes

Explanation of Sample #2:
There are four possible combinations: one is $\{1,1,1\}$ and three are $\{1,1,2\}$. The sum of the scores is $7$.

Data Range:
For $100\%$ of the data, $1 \le k \le n \le 1.2 \times 10^5$, $1 \le a_i \le 10^8$.

见题面 Input 部分

见题面 Output 部分