분할

1부터 n까지 번호가 매겨진 n개의 원소로 이루어진 집합이 주어진다. i-th번째 원소의 가중치는 wi이다. 주어진 집합의 어떤 부분집합의 가중치를 로 나타낸다. 주어진 집합을 k개의 부분집합으로 나눈 어떤 분할 R의 가중치는 이다(주어진 집합의 분할은 그 집합의 부분집합들로 이루어진 집합이며, 주어진 집합의 모든 원소가 분할에 속한 정확히 하나의 부분집합에 포함된다는 것을 상기하라).

주어진 집합을 정확히 k개의 공집합이 아닌 부분집합으로 나누는 모든 분할의 가중치 합을 계산하고, 이를 109 + 7로 나눈 나머지를 출력한다. 두 분할 중 하나에서는 같은 집합에 속하고 다른 분할에서는 서로 다른 집합에 속하는 두 원소 x와 y가 존재할 때, 그리고 그럴 때에만 두 분할은 서로 다른 것으로 간주한다.

첫째 줄에 두 정수 n와 k (1 ≤ k ≤ n ≤ 2·105)가 주어진다. 각각 원소의 개수와 각 분할을 이루는 부분집합의 개수이다.

둘째 줄에 집합 원소들의 가중치인 n개의 정수 wi (1 ≤ wi ≤ 109)가 주어진다.

주어진 집합을 k개의 공집합이 아닌 부분집합으로 나누는 모든 분할의 가중치 합을 109 + 7로 나눈 나머지를 나타내는 정수 하나를 출력한다.

첫 번째 예제에서 가능한 분할은 다음과 같다.

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.