给定一组 n 个元素,索引从 1 到 n。第 i 个元素的权重为 wi。给定集合的某个子集的权重表示为 $$W(S) = |S| \cdot \sum_{i \in S} w_i$$。给定集合的某个分区 R 划分为 k 个子集的权重为 $$W(R) = \sum_{S \in R} W(S)$$ (回想一下,给定集合的分区是其子集的集合,使得给定集合的每个元素恰好属于分区中的一个子集)。
将给定集合的所有分区的权重总和计算为 k 个非空子集,并以 109 + 7 为模进行打印。如果存在两个元素 x 和 y,并且它们在一个分区中属于同一集合,而在另一个分区中属于不同集合,则两个分区被视为不同。
输入
第一行包含两个整数 n 和 k (1 ≤ k ≤ n ≤ 2·105) — 分别是每个分区中的元素数量和子集数量。
第二行包含n个整数wi (1 ≤ wi ≤ 109)——集合中元素的权重。
输出
打印一个整数 — 给定集合的所有分区划分为 k 个非空子集的权重总和,以 109 + 7 为模。
示例
输入 #1
4 2 2 3 2 3
输出 #1
160
输入 #2
5 2 1 2 3 4 5
输出 #2
645
注意
第一个示例中可能的分区:
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;
第二个示例中可能的分区:
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。