#include <bits/stdc++.h>
using namespace std;
template <class T>
void _R(T &x) {
  cin >> x;
}
void _R(int &x) { scanf("%d", &x); }
void _R(int64_t &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template <class T, class... U>
void R(T &head, U &...tail) {
  _R(head);
  R(tail...);
}
template <class T>
void _W(const T &x) {
  cout << x;
}
void _W(const int &x) { printf("%d", x); }
void _W(const int64_t &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template <class T, class U>
void _W(const pair<T, U> &x) {
  _W(x.first);
  putchar(' ');
  _W(x.second);
}
template <class T>
void _W(const vector<T> &x) {
  for (auto i = x.begin(); i != x.end(); _W(*i++))
    if (i != x.cbegin()) putchar(' ');
}
void W() {}
template <class T, class... U>
void W(const T &head, const U &...tail) {
  _W(head);
  putchar(sizeof...(tail) ? ' ' : '\n');
  W(tail...);
}
template <class T, class... U>
void DEBUG(const T &head, const U &...tail) {}
int MOD = 1e9 + 7;
void ADD(int64_t &x, int64_t v) {
  x = (x + v) % MOD;
  if (x < 0) x += MOD;
}
const int SIZE = 1e6 + 10;
int64_t cc[SIZE];
void add(int a, int bb) {
  ADD(cc[bb + 1], -cc[bb]);
  for (int i = bb; i > 0; i--) {
    cc[i] = (cc[i] * a - cc[i - 1]) % MOD;
    if (cc[i] < 0) cc[i] += MOD;
  }
  cc[0] = (cc[0] * a) % MOD;
}
int64_t fac[SIZE], inv[SIZE];
int64_t mypow(int64_t x, int64_t y) {
  int64_t res = 1;
  while (y) {
    if (y & 1) res = res * x % MOD;
    y >>= 1;
    x = x * x % MOD;
  }
  return res;
}
int64_t C(int x, int y) {
  if (y < 0 || y > x) return 0;
  return fac[x] * inv[y] % MOD * inv[x - y] % MOD;
}
void build() {
  assert(MOD >= SIZE);
  fac[0] = 1;
  for (int i = (1); i < (SIZE); ++i) fac[i] = fac[i - 1] * i % MOD;
  inv[SIZE - 1] = mypow(fac[SIZE - 1], MOD - 2);
  for (int i = SIZE - 2; i >= 0; i--) inv[i] = inv[i + 1] * (i + 1) % MOD;
}
void pre() {
  int64_t now = 1, it = 1;
  vector<int> my_fac, my_inv;
  for (int i = 0; i < (102); ++i) {
    int bb = i * 10000000;
    while (it <= bb) {
      now = now * it % MOD;
      it++;
    }
    my_fac.push_back(now);
    my_inv.push_back(mypow(now, MOD - 2));
  }
  printf("pre_fac[102]={");
  for (int i = 0; i < (((int)(my_fac).size())); ++i) printf("%d,", my_fac[i]);
  puts("};");
  printf("pre_inv[102]={");
  for (int i = 0; i < (((int)(my_inv).size())); ++i) printf("%d,", my_inv[i]);
  puts("};");
  exit(0);
}
int64_t pre_fac[102] = {
    1,         682498929, 491101308, 76479948,  723816384, 67347853,  27368307,
    625544428, 199888908, 888050723, 927880474, 281863274, 661224977, 623534362,
    970055531, 261384175, 195888993, 66404266,  547665832, 109838563, 933245637,
    724691727, 368925948, 268838846, 136026497, 112390913, 135498044, 217544623,
    419363534, 500780548, 668123525, 128487469, 30977140,  522049725, 309058615,
    386027524, 189239124, 148528617, 940567523, 917084264, 429277690, 996164327,
    358655417, 568392357, 780072518, 462639908, 275105629, 909210595, 99199382,
    703397904, 733333339, 97830135,  608823837, 256141983, 141827977, 696628828,
    637939935, 811575797, 848924691, 131772368, 724464507, 272814771, 326159309,
    456152084, 903466878, 92255682,  769795511, 373745190, 606241871, 825871994,
    957939114, 435887178, 852304035, 663307737, 375297772, 217598709, 624148346,
    671734977, 624500515, 748510389, 203191898, 423951674, 629786193, 672850561,
    814362881, 823845496, 116667533, 256473217, 627655552, 245795606, 586445753,
    172114298, 193781724, 778983779, 83868974,  315103615, 965785236, 492741665,
    377329025, 847549272, 698611116, 0,
};
int64_t get_inv(int x) {
  if (x < SIZE) return inv[x];
  int64_t now = pre_fac[x / 10000000];
  for (int i = (x / 10000000 * 10000000 + 1); i <= (x); ++i) {
    now = now * i % MOD;
  }
  return mypow(now, MOD - 2);
}
int64_t get_fac(int x) {
  if (x < SIZE) return fac[x];
  int64_t now = pre_fac[x / 10000000];
  for (int i = (x / 10000000 * 10000000 + 1); i <= (x); ++i) {
    now = now * i % MOD;
  }
  return now;
}
int main() {
  build();
  int n, k;
  int64_t tmp = 1;
  R(n, k);
  cc[0] = 1;
  for (int i = 0; i < (n); ++i) {
    int a;
    R(a);
    add(a, i);
    tmp = tmp * a % MOD;
  }
  int64_t res = 0;
  int64_t invv = get_inv(k);
  for (int i = 0; i <= n && i <= k; i++) {
    ADD(res, mypow(n, k - i) * invv % MOD * cc[i]);
    invv = invv * (k - i) % MOD;
  }
  res = res * get_fac(k) % MOD * mypow(mypow(n, k), MOD - 2) % MOD;
  ADD(tmp, -res);
  W(tmp);
  return 0;
}

### Prompt

Create a solution in Cpp for the following problem:

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;
template <class T>
void _R(T &x) {
  cin >> x;
}
void _R(int &x) { scanf("%d", &x); }
void _R(int64_t &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template <class T, class... U>
void R(T &head, U &...tail) {
  _R(head);
  R(tail...);
}
template <class T>
void _W(const T &x) {
  cout << x;
}
void _W(const int &x) { printf("%d", x); }
void _W(const int64_t &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template <class T, class U>
void _W(const pair<T, U> &x) {
  _W(x.first);
  putchar(' ');
  _W(x.second);
}
template <class T>
void _W(const vector<T> &x) {
  for (auto i = x.begin(); i != x.end(); _W(*i++))
    if (i != x.cbegin()) putchar(' ');
}
void W() {}
template <class T, class... U>
void W(const T &head, const U &...tail) {
  _W(head);
  putchar(sizeof...(tail) ? ' ' : '\n');
  W(tail...);
}
template <class T, class... U>
void DEBUG(const T &head, const U &...tail) {}
int MOD = 1e9 + 7;
void ADD(int64_t &x, int64_t v) {
  x = (x + v) % MOD;
  if (x < 0) x += MOD;
}
const int SIZE = 1e6 + 10;
int64_t cc[SIZE];
void add(int a, int bb) {
  ADD(cc[bb + 1], -cc[bb]);
  for (int i = bb; i > 0; i--) {
    cc[i] = (cc[i] * a - cc[i - 1]) % MOD;
    if (cc[i] < 0) cc[i] += MOD;
  }
  cc[0] = (cc[0] * a) % MOD;
}
int64_t fac[SIZE], inv[SIZE];
int64_t mypow(int64_t x, int64_t y) {
  int64_t res = 1;
  while (y) {
    if (y & 1) res = res * x % MOD;
    y >>= 1;
    x = x * x % MOD;
  }
  return res;
}
int64_t C(int x, int y) {
  if (y < 0 || y > x) return 0;
  return fac[x] * inv[y] % MOD * inv[x - y] % MOD;
}
void build() {
  assert(MOD >= SIZE);
  fac[0] = 1;
  for (int i = (1); i < (SIZE); ++i) fac[i] = fac[i - 1] * i % MOD;
  inv[SIZE - 1] = mypow(fac[SIZE - 1], MOD - 2);
  for (int i = SIZE - 2; i >= 0; i--) inv[i] = inv[i + 1] * (i + 1) % MOD;
}
void pre() {
  int64_t now = 1, it = 1;
  vector<int> my_fac, my_inv;
  for (int i = 0; i < (102); ++i) {
    int bb = i * 10000000;
    while (it <= bb) {
      now = now * it % MOD;
      it++;
    }
    my_fac.push_back(now);
    my_inv.push_back(mypow(now, MOD - 2));
  }
  printf("pre_fac[102]={");
  for (int i = 0; i < (((int)(my_fac).size())); ++i) printf("%d,", my_fac[i]);
  puts("};");
  printf("pre_inv[102]={");
  for (int i = 0; i < (((int)(my_inv).size())); ++i) printf("%d,", my_inv[i]);
  puts("};");
  exit(0);
}
int64_t pre_fac[102] = {
    1,         682498929, 491101308, 76479948,  723816384, 67347853,  27368307,
    625544428, 199888908, 888050723, 927880474, 281863274, 661224977, 623534362,
    970055531, 261384175, 195888993, 66404266,  547665832, 109838563, 933245637,
    724691727, 368925948, 268838846, 136026497, 112390913, 135498044, 217544623,
    419363534, 500780548, 668123525, 128487469, 30977140,  522049725, 309058615,
    386027524, 189239124, 148528617, 940567523, 917084264, 429277690, 996164327,
    358655417, 568392357, 780072518, 462639908, 275105629, 909210595, 99199382,
    703397904, 733333339, 97830135,  608823837, 256141983, 141827977, 696628828,
    637939935, 811575797, 848924691, 131772368, 724464507, 272814771, 326159309,
    456152084, 903466878, 92255682,  769795511, 373745190, 606241871, 825871994,
    957939114, 435887178, 852304035, 663307737, 375297772, 217598709, 624148346,
    671734977, 624500515, 748510389, 203191898, 423951674, 629786193, 672850561,
    814362881, 823845496, 116667533, 256473217, 627655552, 245795606, 586445753,
    172114298, 193781724, 778983779, 83868974,  315103615, 965785236, 492741665,
    377329025, 847549272, 698611116, 0,
};
int64_t get_inv(int x) {
  if (x < SIZE) return inv[x];
  int64_t now = pre_fac[x / 10000000];
  for (int i = (x / 10000000 * 10000000 + 1); i <= (x); ++i) {
    now = now * i % MOD;
  }
  return mypow(now, MOD - 2);
}
int64_t get_fac(int x) {
  if (x < SIZE) return fac[x];
  int64_t now = pre_fac[x / 10000000];
  for (int i = (x / 10000000 * 10000000 + 1); i <= (x); ++i) {
    now = now * i % MOD;
  }
  return now;
}
int main() {
  build();
  int n, k;
  int64_t tmp = 1;
  R(n, k);
  cc[0] = 1;
  for (int i = 0; i < (n); ++i) {
    int a;
    R(a);
    add(a, i);
    tmp = tmp * a % MOD;
  }
  int64_t res = 0;
  int64_t invv = get_inv(k);
  for (int i = 0; i <= n && i <= k; i++) {
    ADD(res, mypow(n, k - i) * invv % MOD * cc[i]);
    invv = invv * (k - i) % MOD;
  }
  res = res * get_fac(k) % MOD * mypow(mypow(n, k), MOD - 2) % MOD;
  ADD(tmp, -res);
  W(tmp);
  return 0;
}

```