#include <bits/stdc++.h>
template <int MOD>
struct Integral {
  int v_ = 0;
  template <typename T>
  Integral(T v) : v_(norm(v)) {
    static_assert(std::is_integral<T>::value, "input should be an integral.");
  }
  Integral() = default;
  ~Integral() = default;
  template <typename T>
  T norm(T v) const {
    if (v >= MOD) v -= MOD;
    if (v < 0) v += MOD;
    if (v >= MOD || v < 0) v = (v % MOD + MOD) % MOD;
    return v;
  }
  int val() const { return v_; }
  Integral operator+(const Integral& rhs) const {
    return Integral(val() + rhs.val());
  }
  Integral operator-(const Integral& rhs) const {
    return Integral(val() - rhs.val());
  }
  Integral operator*(const Integral& rhs) const {
    return Integral(val() * 1LL * rhs.val());
  }
  Integral operator/(const Integral& rhs) const { return *this * rhs.inv(); }
  Integral& operator+=(const Integral& rhs) { return *this = *this + rhs; }
  Integral& operator-=(const Integral& rhs) { return *this = *this - rhs; }
  Integral& operator*=(const Integral& rhs) { return *this = *this * rhs; }
  Integral& operator/=(const Integral& rhs) { return *this = *this / rhs; }
  bool operator==(const Integral& rhs) const { return val() == rhs.val(); }
  bool operator!=(const Integral& rhs) const { return !(*this == rhs); }
  const Integral operator-() const { return Integral(-val()); }
  const Integral operator++() {
    v_ = norm(v_ + 1);
    return *this;
  }
  const Integral operator++(int) {
    Integral ret = *this;
    ++(*this);
    return ret;
  }
  const Integral operator--() {
    v_ = norm(v_ - 1);
    return *this;
  }
  const Integral operator--(int) {
    Integral ret = *this;
    --(*this);
    return ret;
  }
  Integral power(long long b) const {
    long long ret = 1 % MOD, a = v_;
    for (; b; b >>= 1, a = a * a % MOD)
      if (b & 1) ret = ret * a % MOD;
    return ret;
  }
  Integral inv() const { return power(MOD - 2); }
};
template <int MOD>
std::string to_string(const Integral<MOD>& v) {
  return std::string("Integral{v=") + std::to_string(v.val()) + "}";
}
template <int MOD, bool kAllowBruteForce = false>
struct Binomial {
  std::vector<Integral<MOD>> factor, inv_factor;
  explicit Binomial(int n = 0) : factor(n + 1), inv_factor(n + 1) {
    factor[0] = 1;
    for (int i = 1; i <= n; ++i) factor[i] = factor[i - 1] * i;
    inv_factor[n] = factor[n].inv();
    for (int i = n; i >= 1; --i) inv_factor[i - 1] = inv_factor[i] * i;
  }
  ~Binomial() = default;
  template <typename T>
  Integral<MOD> operator()(T a, T b) const {
    if (a < b || b < 0) return 0;
    if (a < factor.size()) return factor[a] * inv_factor[b] * inv_factor[a - b];
    if constexpr (!kAllowBruteForce) {
      throw std::out_of_range("Binomial");
    } else {
      b = std::min(b, a - b);
      Integral<MOD> ret = 1;
      for (T i = 1; i <= b; ++i) ret = ret * (a + 1 - i) / i;
      return ret;
    }
  }
};
template <int MOD>
struct PowerTable : public std::vector<Integral<MOD>> {
  PowerTable(int n, const Integral<MOD>& g) {
    static_assert(sizeof(PowerTable) == sizeof(std::vector<Integral<MOD>>), "");
    this->resize(n + 1);
    this->at(0) = 1;
    this->at(1) = g;
    for (int i = 2; i < this->size(); ++i)
      this->at(i) = this->at(i - 1) * this->at(1);
  }
};
const int MOD = 1e9 + 7;
using Mint = Integral<MOD>;
using Binom = Binomial<MOD>;
Binom binom(200000);
Mint stirling(int n, int k) {
  Mint ret = 0;
  for (int j = 0; j <= k; ++j) {
    ret += Mint(j & 1 ? -1 : 1) * binom(k, j) * Mint(k - j).power(n);
  }
  ret *= binom.inv_factor[k];
  return ret;
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::istream& reader = std::cin;
  int n, k;
  reader >> n >> k;
  Mint sum = 0;
  for (int i = 0; i < n; ++i) {
    int x;
    reader >> x;
    sum += x;
  }
  Mint result = sum * (stirling(n - 1, k) * (n - 1) + stirling(n, k));
  printf("%d\n", result.val());
}

### Prompt

Your task is to create a Cpp solution to the following problem:

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>
template <int MOD>
struct Integral {
  int v_ = 0;
  template <typename T>
  Integral(T v) : v_(norm(v)) {
    static_assert(std::is_integral<T>::value, "input should be an integral.");
  }
  Integral() = default;
  ~Integral() = default;
  template <typename T>
  T norm(T v) const {
    if (v >= MOD) v -= MOD;
    if (v < 0) v += MOD;
    if (v >= MOD || v < 0) v = (v % MOD + MOD) % MOD;
    return v;
  }
  int val() const { return v_; }
  Integral operator+(const Integral& rhs) const {
    return Integral(val() + rhs.val());
  }
  Integral operator-(const Integral& rhs) const {
    return Integral(val() - rhs.val());
  }
  Integral operator*(const Integral& rhs) const {
    return Integral(val() * 1LL * rhs.val());
  }
  Integral operator/(const Integral& rhs) const { return *this * rhs.inv(); }
  Integral& operator+=(const Integral& rhs) { return *this = *this + rhs; }
  Integral& operator-=(const Integral& rhs) { return *this = *this - rhs; }
  Integral& operator*=(const Integral& rhs) { return *this = *this * rhs; }
  Integral& operator/=(const Integral& rhs) { return *this = *this / rhs; }
  bool operator==(const Integral& rhs) const { return val() == rhs.val(); }
  bool operator!=(const Integral& rhs) const { return !(*this == rhs); }
  const Integral operator-() const { return Integral(-val()); }
  const Integral operator++() {
    v_ = norm(v_ + 1);
    return *this;
  }
  const Integral operator++(int) {
    Integral ret = *this;
    ++(*this);
    return ret;
  }
  const Integral operator--() {
    v_ = norm(v_ - 1);
    return *this;
  }
  const Integral operator--(int) {
    Integral ret = *this;
    --(*this);
    return ret;
  }
  Integral power(long long b) const {
    long long ret = 1 % MOD, a = v_;
    for (; b; b >>= 1, a = a * a % MOD)
      if (b & 1) ret = ret * a % MOD;
    return ret;
  }
  Integral inv() const { return power(MOD - 2); }
};
template <int MOD>
std::string to_string(const Integral<MOD>& v) {
  return std::string("Integral{v=") + std::to_string(v.val()) + "}";
}
template <int MOD, bool kAllowBruteForce = false>
struct Binomial {
  std::vector<Integral<MOD>> factor, inv_factor;
  explicit Binomial(int n = 0) : factor(n + 1), inv_factor(n + 1) {
    factor[0] = 1;
    for (int i = 1; i <= n; ++i) factor[i] = factor[i - 1] * i;
    inv_factor[n] = factor[n].inv();
    for (int i = n; i >= 1; --i) inv_factor[i - 1] = inv_factor[i] * i;
  }
  ~Binomial() = default;
  template <typename T>
  Integral<MOD> operator()(T a, T b) const {
    if (a < b || b < 0) return 0;
    if (a < factor.size()) return factor[a] * inv_factor[b] * inv_factor[a - b];
    if constexpr (!kAllowBruteForce) {
      throw std::out_of_range("Binomial");
    } else {
      b = std::min(b, a - b);
      Integral<MOD> ret = 1;
      for (T i = 1; i <= b; ++i) ret = ret * (a + 1 - i) / i;
      return ret;
    }
  }
};
template <int MOD>
struct PowerTable : public std::vector<Integral<MOD>> {
  PowerTable(int n, const Integral<MOD>& g) {
    static_assert(sizeof(PowerTable) == sizeof(std::vector<Integral<MOD>>), "");
    this->resize(n + 1);
    this->at(0) = 1;
    this->at(1) = g;
    for (int i = 2; i < this->size(); ++i)
      this->at(i) = this->at(i - 1) * this->at(1);
  }
};
const int MOD = 1e9 + 7;
using Mint = Integral<MOD>;
using Binom = Binomial<MOD>;
Binom binom(200000);
Mint stirling(int n, int k) {
  Mint ret = 0;
  for (int j = 0; j <= k; ++j) {
    ret += Mint(j & 1 ? -1 : 1) * binom(k, j) * Mint(k - j).power(n);
  }
  ret *= binom.inv_factor[k];
  return ret;
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::istream& reader = std::cin;
  int n, k;
  reader >> n >> k;
  Mint sum = 0;
  for (int i = 0; i < n; ++i) {
    int x;
    reader >> x;
    sum += x;
  }
  Mint result = sum * (stirling(n - 1, k) * (n - 1) + stirling(n, k));
  printf("%d\n", result.val());
}

```