CF961G.Partitions

You are given a set of n elements indexed from 1 to n. The weight of i-th element is w__i. The weight of some subset of a given set is denoted as . The weight of some partition R of a given set into k subsets is (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.

给你一个包含 $n$ 个元素的集合，元素编号从 $1$ 到 $n$。第 $i$ 个元素的权重为 $w_i$。某个给定集合的子集 $S$ 的权重定义为
。
给定集合的一个划分为 $k$ 个子集的划分 $R$（即：将该集合拆分为 $k$ 个互不相交、非空且并集为全集的子集）的权重定义为

（注意：集合的一个划分是指其若干子集构成的集合，使得原集合中的每个元素恰好属于其中一个子集）。

请计算所有将给定集合划分为恰好 $k$ 个非空子集的划分的权重之和，并将结果对 $10^9 + 7$ 取模后输出。
若存在两个元素 $x$ 和 $y$，使得它们在某一个划分中属于同一子集，而在另一个划分中属于不同子集，则认为这两个划分不同。

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 w__i (1 ≤ w__i ≤ 109)— weights of elements of the set.

第一行包含两个整数 $n$ 和 $k$（$1 ≤ k ≤ n ≤ 2·10^5$），分别表示元素个数和每个划分中子集的个数。

第二行包含 $n$ 个整数 $w_i$（$1 ≤ w_i ≤ 10^9$），表示集合中各元素的权重。

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

输出一个整数——将给定集合划分为 $k$ 个非空子集的所有划分方式的权重之和，对 $10^9 + 7$ 取模。

Possible partitions in the first sample:

1. {{1, 2, 3}, {4}}, W(R) = 3·(_w_1 + _w_2 + _w_3) + 1·_w_4 = 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·(_w_1 + _w_2) + 2·(_w_3 + _w_4) = 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.

第一个样例中的可能划分：

1. {{1, 2, 3}, {4}}, W(R) = 3·(_w_1 + _w_2 + _w_3) + 1·_w_4 = 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·(_w_1 + _w_2) + 2·(_w_3 + _w_4) = 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;

第二个样例中的可能划分：

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.