Partitions

题意翻译

给出 $n$ 个物品,每个物品有一个权值 $w_i$。 定义一个集合 $S$ 的权值 $W(S)=|S|\sum\limits_{x\in S}w_x$。 定义一个划分的权值为 $W'(R)=\sum\limits_{S\in R}W(S)$。 求将 $n$ 个物品划分成 $k$ 个集合的所有方案的权值和。答案对 $10^9+7$ 取模。 $n,k\le2\times10^5$,$w_i\le10^9$。 感谢 @Kelin 提供的翻译

题目描述

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 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF961G/fbf0c843290b6183affbaf7ada0d6cecd6d2fbbd.png). The weight of some partition $ R $ of a given set into $ k $ subsets is ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF961G/0aeb77393cfc4b9aa3d9c64303202277f9c1f051.png) (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 $ 10^{9}+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.

输入输出格式

输入格式


The first line contains two integers $ n $ and $ k $ ( $ 1<=k<=n<=2·10^{5} $ ) — the number of elements and the number of subsets in each partition, respectively. The second line contains $ n $ integers $ w_{i} $ ( $ 1<=w_{i}<=10^{9} $ )— weights of elements of the set.

输出格式


Print one integer — the sum of weights of all partitions of a given set into $ k $ non-empty subsets, taken modulo $ 10^{9}+7 $ .

输入输出样例

输入样例 #1

4 2
2 3 2 3

输出样例 #1

160

输入样例 #2

5 2
1 2 3 4 5

输出样例 #2

645

说明

Possible partitions in the first sample: 1. $ \{\{1,2,3\},\{4\}\} $ , $ W(R)=3\cdot(w_{1}+w_{2}+w_{3})+1\cdot 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\cdot(w_{1}+w_{2})+2\cdot(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 $ .