Partitions
Contest: Educational Codeforces Round 41 (Rated for Div. 2)
Difficulty rating: 2700
Tags: combinatorics, math, number theory

You are given a set of n elements indexed from 1 to n. The weight of i-th element is wi. The weight of some subset of a given set is denoted as $$W(S) = |S| \cdot \sum_{i \in S} w_i$$. The weight of some partition R of a given set into k subsets is $$W(R) = \sum_{S \in R} W(S)$$ (recall that a partition of a given set is a set of its subsets such that every element of the given set belongs to exactly one subset in partition).

Calculate the sum of weights of all partitions of a given set into exactly k non-empty subsets, and print it modulo 109 + 7. Two partitions are considered different iff there exist two elements x and y such that they belong to the same set in one of the partitions, and to different sets in another partition.

Input format:
The first line contains two integers n and k (1 ≤ k ≤ n ≤ 2·105) — the number of elements and the number of subsets in each partition, respectively.

The second line contains n integers wi (1 ≤ wi ≤ 109)— weights of elements of the set.

Output format:
Print one integer — the sum of weights of all partitions of a given set into k non-empty subsets, taken modulo 109 + 7.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
Possible partitions in the first sample:

1. {{1, 2, 3}, {4}}, W(R) = 3·(w1 + w2 + w3) + 1·w4 = 24;
2. {{1, 2, 4}, {3}}, W(R) = 26;
3. {{1, 3, 4}, {2}}, W(R) = 24;
4. {{1, 2}, {3, 4}}, W(R) = 2·(w1 + w2) + 2·(w3 + w4) = 20;
5. {{1, 3}, {2, 4}}, W(R) = 20;
6. {{1, 4}, {2, 3}}, W(R) = 20;
7. {{1}, {2, 3, 4}}, W(R) = 26;

Possible partitions in the second sample:

1. {{1, 2, 3, 4}, {5}}, W(R) = 45;
2. {{1, 2, 3, 5}, {4}}, W(R) = 48;
3. {{1, 2, 4, 5}, {3}}, W(R) = 51;
4. {{1, 3, 4, 5}, {2}}, W(R) = 54;
5. {{2, 3, 4, 5}, {1}}, W(R) = 57;
6. {{1, 2, 3}, {4, 5}}, W(R) = 36;
7. {{1, 2, 4}, {3, 5}}, W(R) = 37;
8. {{1, 2, 5}, {3, 4}}, W(R) = 38;
9. {{1, 3, 4}, {2, 5}}, W(R) = 38;
10. {{1, 3, 5}, {2, 4}}, W(R) = 39;
11. {{1, 4, 5}, {2, 3}}, W(R) = 40;
12. {{2, 3, 4}, {1, 5}}, W(R) = 39;
13. {{2, 3, 5}, {1, 4}}, W(R) = 40;
14. {{2, 4, 5}, {1, 3}}, W(R) = 41;
15. {{3, 4, 5}, {1, 2}}, W(R) = 42.

Example input:
4 2
2 3 2 3

Example output:
160

Example input:
5 2
1 2 3 4 5

Example output:
645

Editorial:
Let's look at some facts. At first, the answer is the sum of weights wi taken with some coefficients cfi. So, it's enough to calculate those coefficients.
Then cfi can be calculated by iterating on the size of the subset containing i-th element: $${ c f } _ { i } = \sum _ { s i z e = 1 } ^ { s i z e = n + 1 - k } s i z e \cdot f ( n, k, s i z e )$$, where f(n, k, size) is the number of partitions of set with n elements into k nonempty subsets with one subset of fixed size size where i belongs.
This solution is still quite slow, so the next fact is: if two elements i and j belong to the same subset, then j "increases" the coefficient before wi. So for each element i we can iterate over all elements j which will lie in one subset with i. In other words, $$cf_i = \sum_{j=1}^{j=n} g(n,k,i,j) = g(n,k,i,i) + \sum_{j\neq i} g(n,k,i,j)$$. g(n, k, i, j) is the number of ways to divide set with n elements into k subsets in such a way that elements i and j wil lie in one subset.
g(n, k, i, j) can be calculated using Stirling numbers of the second kind: let $${\binom {n}{k}}$$ be the number of partitions of set with n elements into k non-empty subsets. If i = j then $$g(n,k,i,j) = \left\{ {n \atop k} \right\}$$, else we just merge i and j into one element and let $$g(n,k,i,j) = \left\{ {n-1 \atop k} \right\}$$.
Final formula is $$c f_i = \binom{n}{k} + \sum_{j \neq i} \binom{n-1}{k} = \binom{n}{k} + (n-1) \cdot \binom{n-1}{k}$$. And the answer is $$\sum_{i=1}^{n} w_i \cdot c f_i = c f_0 \sum_{i=1}^{n} w_i$$.
Counting Stirling numbers can be done with inclusion-exclusion principle or by searching Wiki: $${ \left\{ \begin{matrix} n \\ k \end{matrix} \right\} } = { \frac { 1 } { k! } } \sum _ { j=0 } ^ { j=k } ( - 1 ) ^ { k + j } { \binom { k } { j } } j ^ { n }$$.
Resulting complexity is O(nlog(n)).