Problem Description

In the magical land of Xiao Ben, there is a toxic coach named Xiao Ben.

Xiao Ben is passionate about multiplication. His favorite activity is to select $K$ numbers from a sequence of $N$ elements (note: you cannot select the same element multiple times, but selecting different elements with the same value is allowed) and calculate the product of these $K$ numbers as the score for this combination.

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

Xiao Ben (in some aspects) is quite merciful, so you don't need to write high precision. Just output the result 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

A single line containing one 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

Notes

Sample #2 Explanation:

Xiao Ben can choose the following 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 sum is $7$.

Data Range:

For 10% of the data, $N \le 5000, K \le 2$;

For 30% of the data, $N \le 10^5, K \le 3$;

For 50% of the data, $N \le 10^5, K \le 5$;

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

见题面 Input 部分

见题面 Output 部分