#include <bits/stdc++.h>
std::mt19937 rng(
    (int)std::chrono::steady_clock::now().time_since_epoch().count());
const int MOD = 1e9 + 7;
template <class T>
T fexp(T x, long long e) {
  T ans(1);
  for (; e > 0; e /= 2) {
    if (e & 1) ans = ans * x;
    x = x * x;
  }
  return ans;
}
template <int mod = MOD>
struct modBase {
  modBase(int v = 0) : val(v < 0 ? v + mod : v) {}
  int val;
  void operator+=(modBase<mod> o) { *this = *this + o; }
  void operator-=(modBase<mod> o) { *this = *this - o; }
  void operator*=(modBase<mod> o) { *this = *this * o; }
  modBase<mod> operator*(modBase<mod> o) {
    return (int)((long long)val * o.val % mod);
  }
  modBase<mod> operator+(modBase<mod> o) {
    return val + o.val >= mod ? val + o.val - mod : val + o.val;
  }
  modBase<mod> operator-(modBase<mod> o) {
    return val - o.val < 0 ? val - o.val + mod : val - o.val;
  }
  friend std::ostream &operator<<(std::ostream &os, const modBase<mod> &p) {
    return os << p.val;
  }
  friend std::istream &operator>>(std::istream &is, modBase<mod> &p) {
    return is >> p.val;
  }
};
template <class T>
std::vector<T> partitionNumber(int n) {
  std::vector<T> ans(n, 0);
  ans[0] = 1;
  for (int i = 1; i < n; i++) {
    for (int j = 1; j * (3 * j + 1) / 2 <= i; j++) {
      ans[i] = ((j & 1) ? ans[i] + ans[i - j * (3 * j + 1) / 2]
                        : ans[i] - ans[i - j * (3 * j + 1) / 2]);
    }
    for (int j = 1; j * (3 * j - 1) / 2 <= i; j++) {
      ans[i] = ((j & 1) ? ans[i] + ans[i - j * (3 * j - 1) / 2]
                        : ans[i] - ans[i - j * (3 * j - 1) / 2]);
    }
  }
  return ans;
}
const int ms = 200200;
modBase<> fat[ms], ifat[ms];
void initComb() {
  fat[0] = 1;
  for (int i = 1; i < ms; i++) {
    fat[i] = fat[i - 1] * i;
  }
  ifat[ms - 1] = fexp(fat[ms - 1], MOD - 2);
  for (int i = ms - 1; i > 0; i--) {
    ifat[i - 1] = ifat[i] * i;
  }
}
modBase<> comb(int n, int a) {
  return a < 0 || a > n ? modBase<>(0) : fat[n] * ifat[a] * ifat[n - a];
}
int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(NULL);
  initComb();
  int n, k;
  std::cin >> n >> k;
  k--;
  modBase<> sum(0);
  for (int i = 0; i < n; i++) {
    int x;
    std::cin >> x;
    sum += x;
  }
  modBase<> other(0);
  for (int i = 0; i <= k; i++) {
    modBase<> cur = (k - i) % 2 ? -1 : 1;
    cur *= comb(k, i);
    cur *= fexp(modBase<>(i + 1), n - 2) *
           (modBase<>(i + 1) * n - modBase<>(i) * (n - 1));
    other += cur;
  }
  std::cout << sum * other * ifat[k] << '\n';
}

### Prompt

Develop a solution in cpp to the problem described below:

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 <image>. The weight of some partition R of a given set into k subsets is <image> (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

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

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

Examples

Input

4 2
2 3 2 3


Output

160


Input

5 2
1 2 3 4 5


Output

645

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. 

### Response

```cpp
#include <bits/stdc++.h>
std::mt19937 rng(
    (int)std::chrono::steady_clock::now().time_since_epoch().count());
const int MOD = 1e9 + 7;
template <class T>
T fexp(T x, long long e) {
  T ans(1);
  for (; e > 0; e /= 2) {
    if (e & 1) ans = ans * x;
    x = x * x;
  }
  return ans;
}
template <int mod = MOD>
struct modBase {
  modBase(int v = 0) : val(v < 0 ? v + mod : v) {}
  int val;
  void operator+=(modBase<mod> o) { *this = *this + o; }
  void operator-=(modBase<mod> o) { *this = *this - o; }
  void operator*=(modBase<mod> o) { *this = *this * o; }
  modBase<mod> operator*(modBase<mod> o) {
    return (int)((long long)val * o.val % mod);
  }
  modBase<mod> operator+(modBase<mod> o) {
    return val + o.val >= mod ? val + o.val - mod : val + o.val;
  }
  modBase<mod> operator-(modBase<mod> o) {
    return val - o.val < 0 ? val - o.val + mod : val - o.val;
  }
  friend std::ostream &operator<<(std::ostream &os, const modBase<mod> &p) {
    return os << p.val;
  }
  friend std::istream &operator>>(std::istream &is, modBase<mod> &p) {
    return is >> p.val;
  }
};
template <class T>
std::vector<T> partitionNumber(int n) {
  std::vector<T> ans(n, 0);
  ans[0] = 1;
  for (int i = 1; i < n; i++) {
    for (int j = 1; j * (3 * j + 1) / 2 <= i; j++) {
      ans[i] = ((j & 1) ? ans[i] + ans[i - j * (3 * j + 1) / 2]
                        : ans[i] - ans[i - j * (3 * j + 1) / 2]);
    }
    for (int j = 1; j * (3 * j - 1) / 2 <= i; j++) {
      ans[i] = ((j & 1) ? ans[i] + ans[i - j * (3 * j - 1) / 2]
                        : ans[i] - ans[i - j * (3 * j - 1) / 2]);
    }
  }
  return ans;
}
const int ms = 200200;
modBase<> fat[ms], ifat[ms];
void initComb() {
  fat[0] = 1;
  for (int i = 1; i < ms; i++) {
    fat[i] = fat[i - 1] * i;
  }
  ifat[ms - 1] = fexp(fat[ms - 1], MOD - 2);
  for (int i = ms - 1; i > 0; i--) {
    ifat[i - 1] = ifat[i] * i;
  }
}
modBase<> comb(int n, int a) {
  return a < 0 || a > n ? modBase<>(0) : fat[n] * ifat[a] * ifat[n - a];
}
int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(NULL);
  initComb();
  int n, k;
  std::cin >> n >> k;
  k--;
  modBase<> sum(0);
  for (int i = 0; i < n; i++) {
    int x;
    std::cin >> x;
    sum += x;
  }
  modBase<> other(0);
  for (int i = 0; i <= k; i++) {
    modBase<> cur = (k - i) % 2 ? -1 : 1;
    cur *= comb(k, i);
    cur *= fexp(modBase<>(i + 1), n - 2) *
           (modBase<>(i + 1) * n - modBase<>(i) * (n - 1));
    other += cur;
  }
  std::cout << sum * other * ifat[k] << '\n';
}

```