Combination Product Sum

Given a multiset of n integers and an integer k, your task is to compute the sum of the products of all combinations of k numbers chosen from the multiset. In other words, if the multiset is \(\{a_1, a_2, \dots, a_n\}\), you need to calculate:

[ S = \sum_{\substack{S \subseteq {1,2,\dots,n} \ |S|=k}} \prod_{i \in S} a_i \mod (10^9+7) ]

Since the answer can be very large, output the result modulo \(10^9+7\).

inputFormat

The first line contains two integers n and k (1 ≤ k ≤ n ≤ 10⁵), representing the number of elements in the multiset and the number of elements to choose respectively.

The second line contains n integers \(a_1, a_2, \dots, a_n\) (\(-10^9 \leq a_i \leq 10^9\)), which are the elements of the multiset.

outputFormat

Output a single integer, the sum of the products of all \(k\)-element combinations taken from the given multiset, modulo \(10^9+7\).

sample

3 2
1 2 3

11