Sum of Products of Combinations

You are given a sequence of N integers and an integer K. Your task is to choose K distinct elements from the sequence (note: you cannot choose the same element more than once, although elements with equal values are allowed to be chosen if they occupy different positions), and compute the product of the selected numbers. The score for a particular combination is the product of its K numbers. You need to sum up the scores for all possible combinations and output the result modulo \(10^9+7\).

This is equivalent to computing the Kth elementary symmetric sum of the sequence.

For example, if N = 3, K = 2 and the sequence is [1, 2, 3], then the valid combinations are:

• 1 * 2 = 2
• 1 * 3 = 3
• 2 * 3 = 6

The answer is \(2+3+6=11\) modulo \(10^9+7\).

inputFormat

The first line contains two integers N and K separated by a space.

The second line contains N space-separated integers, representing the sequence.

outputFormat

Output one integer: the sum of the products of all combinations of K numbers chosen from the sequence, taken modulo \(10^9+7\).

sample

3 2
1 2 3

11