#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using uint = unsigned int;
template <class T>
using V = vector<T>;
template <class T>
using VV = vector<vector<T>>;
template <class T, class U>
void chmax(T& x, U y) {
  if (x < y) x = y;
}
template <class T, class U>
void chmin(T& x, U y) {
  if (y < x) x = y;
}
template <class T>
void mkuni(V<T>& v) {
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
}
template <class S, class T>
ostream& operator<<(ostream& o, const pair<S, T>& p) {
  return o << "(" << p.first << "," << p.second << ")";
}
template <class T>
ostream& operator<<(ostream& o, const vector<T>& vc) {
  o << "{";
  for (const T& v : vc) o << v << ",";
  o << "}";
  return o;
}
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }
template <unsigned int mod_>
struct ModInt {
  using uint = unsigned int;
  using ll = long long;
  using ull = unsigned long long;
  constexpr static uint mod = mod_;
  uint v;
  ModInt() : v(0) {}
  ModInt(ll _v) : v(normS(_v % mod + mod)) {}
  explicit operator bool() const { return v != 0; }
  static uint normS(const uint& x) { return (x < mod) ? x : x - mod; }
  static ModInt make(const uint& x) {
    ModInt m;
    m.v = x;
    return m;
  }
  ModInt operator+(const ModInt& b) const { return make(normS(v + b.v)); }
  ModInt operator-(const ModInt& b) const { return make(normS(v + mod - b.v)); }
  ModInt operator-() const { return make(normS(mod - v)); }
  ModInt operator*(const ModInt& b) const { return make((ull)v * b.v % mod); }
  ModInt operator/(const ModInt& b) const { return *this * b.inv(); }
  ModInt& operator+=(const ModInt& b) { return *this = *this + b; }
  ModInt& operator-=(const ModInt& b) { return *this = *this - b; }
  ModInt& operator*=(const ModInt& b) { return *this = *this * b; }
  ModInt& operator/=(const ModInt& b) { return *this = *this / b; }
  ModInt& operator++(int) { return *this = *this + 1; }
  ModInt& operator--(int) { return *this = *this - 1; }
  ll extgcd(ll a, ll b, ll& x, ll& y) const {
    ll p[] = {a, 1, 0}, q[] = {b, 0, 1};
    while (*q) {
      ll t = *p / *q;
      for (int i = 0; i < int(3); i++) swap(p[i] -= t * q[i], q[i]);
    }
    if (p[0] < 0)
      for (int i = 0; i < int(3); i++) p[i] = -p[i];
    x = p[1], y = p[2];
    return p[0];
  }
  ModInt inv() const {
    ll x, y;
    extgcd(v, mod, x, y);
    return make(normS(x + mod));
  }
  ModInt pow(ll p) const {
    if (p < 0) return inv().pow(-p);
    ModInt a = 1;
    ModInt x = *this;
    while (p) {
      if (p & 1) a *= x;
      x *= x;
      p >>= 1;
    }
    return a;
  }
  bool operator==(const ModInt& b) const { return v == b.v; }
  bool operator!=(const ModInt& b) const { return v != b.v; }
  friend istream& operator>>(istream& o, ModInt& x) {
    ll tmp;
    o >> tmp;
    x = ModInt(tmp);
    return o;
  }
  friend ostream& operator<<(ostream& o, const ModInt& x) { return o << x.v; }
};
using mint = ModInt<1000000007>;
V<mint> fact, ifact;
mint Choose(int a, int b) {
  if (b < 0 || a < b) return 0;
  return fact[a] * ifact[b] * ifact[a - b];
}
void InitFact(int N) {
  fact.resize(N);
  ifact.resize(N);
  fact[0] = 1;
  for (int i = 1; i <= int(N - 1); i++) fact[i] = fact[i - 1] * i;
  ifact[N - 1] = fact[N - 1].inv();
  for (int i = N - 2; i >= 0; i--) ifact[i] = ifact[i + 1] * (i + 1);
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(20);
  int N, K;
  cin >> N >> K;
  V<mint> f(N + 1);
  {
    f[0] = 1;
    for (int i = 0; i < int(N); i++) {
      V<mint> g(N + 1);
      mint a;
      cin >> a;
      for (int j = 0; j < int(N + 1); j++)
        if (f[j]) {
          g[j] += f[j];
          g[j + 1] += f[j] * a;
        }
      f = g;
    }
  }
  void(0);
  for (int i = 0; i < int(N + 1); i++) f[i] *= N - i;
  V<mint> way(N);
  for (int h = 0; h < int(N); h++) {
    way[h] = 1;
    for (int i = 0; i < int(h + 1); i++) way[h] *= K - i;
    way[h] /= h + 1;
  }
  void(0);
  mint ans = 0;
  for (int sel = 0; sel < int(N); sel++) {
    int h = N - 1 - sel;
    ans += f[sel] * way[h] * mint(-N).pow(-h);
  }
  cout << ans / N << endl;
  void(0);
}

### Prompt

Construct a Cpp code solution to the problem outlined:

A false witness that speaketh lies!

You are given a sequence containing n integers. There is a variable res that is equal to 0 initially. The following process repeats k times.

Choose an index from 1 to n uniformly at random. Name it x. Add to res the multiply of all ai's such that 1 ≤ i ≤ n, but i ≠ x. Then, subtract ax by 1.

You have to find expected value of res at the end of the process. It can be proved that the expected value of res can be represented as an irreducible fraction <image>. You have to find <image>.

Input

The first line contains two integers n and k (1 ≤ n ≤ 5000, 1 ≤ k ≤ 109) — the number of elements and parameter k that is specified in the statement.

The second line contains n space separated integers a1, a2, ..., an (0 ≤ ai ≤ 109).

Output

Output a single integer — the value <image>.

Examples

Input

2 1
5 5


Output

5

Input

1 10
80


Output

10

Input

2 2
0 0


Output

500000003

Input

9 4
0 11 12 9 20 7 8 18 2


Output

169316356

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using uint = unsigned int;
template <class T>
using V = vector<T>;
template <class T>
using VV = vector<vector<T>>;
template <class T, class U>
void chmax(T& x, U y) {
  if (x < y) x = y;
}
template <class T, class U>
void chmin(T& x, U y) {
  if (y < x) x = y;
}
template <class T>
void mkuni(V<T>& v) {
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
}
template <class S, class T>
ostream& operator<<(ostream& o, const pair<S, T>& p) {
  return o << "(" << p.first << "," << p.second << ")";
}
template <class T>
ostream& operator<<(ostream& o, const vector<T>& vc) {
  o << "{";
  for (const T& v : vc) o << v << ",";
  o << "}";
  return o;
}
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }
template <unsigned int mod_>
struct ModInt {
  using uint = unsigned int;
  using ll = long long;
  using ull = unsigned long long;
  constexpr static uint mod = mod_;
  uint v;
  ModInt() : v(0) {}
  ModInt(ll _v) : v(normS(_v % mod + mod)) {}
  explicit operator bool() const { return v != 0; }
  static uint normS(const uint& x) { return (x < mod) ? x : x - mod; }
  static ModInt make(const uint& x) {
    ModInt m;
    m.v = x;
    return m;
  }
  ModInt operator+(const ModInt& b) const { return make(normS(v + b.v)); }
  ModInt operator-(const ModInt& b) const { return make(normS(v + mod - b.v)); }
  ModInt operator-() const { return make(normS(mod - v)); }
  ModInt operator*(const ModInt& b) const { return make((ull)v * b.v % mod); }
  ModInt operator/(const ModInt& b) const { return *this * b.inv(); }
  ModInt& operator+=(const ModInt& b) { return *this = *this + b; }
  ModInt& operator-=(const ModInt& b) { return *this = *this - b; }
  ModInt& operator*=(const ModInt& b) { return *this = *this * b; }
  ModInt& operator/=(const ModInt& b) { return *this = *this / b; }
  ModInt& operator++(int) { return *this = *this + 1; }
  ModInt& operator--(int) { return *this = *this - 1; }
  ll extgcd(ll a, ll b, ll& x, ll& y) const {
    ll p[] = {a, 1, 0}, q[] = {b, 0, 1};
    while (*q) {
      ll t = *p / *q;
      for (int i = 0; i < int(3); i++) swap(p[i] -= t * q[i], q[i]);
    }
    if (p[0] < 0)
      for (int i = 0; i < int(3); i++) p[i] = -p[i];
    x = p[1], y = p[2];
    return p[0];
  }
  ModInt inv() const {
    ll x, y;
    extgcd(v, mod, x, y);
    return make(normS(x + mod));
  }
  ModInt pow(ll p) const {
    if (p < 0) return inv().pow(-p);
    ModInt a = 1;
    ModInt x = *this;
    while (p) {
      if (p & 1) a *= x;
      x *= x;
      p >>= 1;
    }
    return a;
  }
  bool operator==(const ModInt& b) const { return v == b.v; }
  bool operator!=(const ModInt& b) const { return v != b.v; }
  friend istream& operator>>(istream& o, ModInt& x) {
    ll tmp;
    o >> tmp;
    x = ModInt(tmp);
    return o;
  }
  friend ostream& operator<<(ostream& o, const ModInt& x) { return o << x.v; }
};
using mint = ModInt<1000000007>;
V<mint> fact, ifact;
mint Choose(int a, int b) {
  if (b < 0 || a < b) return 0;
  return fact[a] * ifact[b] * ifact[a - b];
}
void InitFact(int N) {
  fact.resize(N);
  ifact.resize(N);
  fact[0] = 1;
  for (int i = 1; i <= int(N - 1); i++) fact[i] = fact[i - 1] * i;
  ifact[N - 1] = fact[N - 1].inv();
  for (int i = N - 2; i >= 0; i--) ifact[i] = ifact[i + 1] * (i + 1);
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(20);
  int N, K;
  cin >> N >> K;
  V<mint> f(N + 1);
  {
    f[0] = 1;
    for (int i = 0; i < int(N); i++) {
      V<mint> g(N + 1);
      mint a;
      cin >> a;
      for (int j = 0; j < int(N + 1); j++)
        if (f[j]) {
          g[j] += f[j];
          g[j + 1] += f[j] * a;
        }
      f = g;
    }
  }
  void(0);
  for (int i = 0; i < int(N + 1); i++) f[i] *= N - i;
  V<mint> way(N);
  for (int h = 0; h < int(N); h++) {
    way[h] = 1;
    for (int i = 0; i < int(h + 1); i++) way[h] *= K - i;
    way[h] /= h + 1;
  }
  void(0);
  mint ans = 0;
  for (int sel = 0; sel < int(N); sel++) {
    int h = N - 1 - sel;
    ans += f[sel] * way[h] * mint(-N).pow(-h);
  }
  cout << ans / N << endl;
  void(0);
}

```