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 *a*<sub class="lower-index">*i*</sub>'s such that 1 ≤ *i* ≤ *n*, but *i* ≠ *x*. Then, subtract *a*<sub class="lower-index">*x*</sub> 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 <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/b795551c4ba5b501281e7063ac11feb87c7f234f.png" style="max-width: 100.0%;max-height: 100.0%;"/>. You have to find <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/e6387465bd69e039151b5354601d2488d4ec2099.png" style="max-width: 100.0%;max-height: 100.0%;"/>.
The first line contains two integers *n* and *k* (1 ≤ *n* ≤ 5000, 1 ≤ *k* ≤ 10<sup class="upper-index">9</sup>) — the number of elements and parameter *k* that is specified in the statement.

The second line contains *n* space separated integers *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> (0 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>).
none
2 1
5 5
5
1 10
80
10
2 2
0 0
500000003
9 4
0 11 12 9 20 7 8 18 2
169316356
5 1
14 2 0 0 1
0
2 4
0 16
29
7 2
0 9 4 0 7 14 4
999999431
10 3
12 15 19 16 19 0 4 3 5 11
727205525
3 3
18 7 17
222222747
8 3
20 15 1 4 20 16 6 12
15570669
7 405871919
4 4 12 5 7 10 10
873805235
2 753394402
3 15
220969232
2 34825250
10 12
384515834
5 585751779
18 17 6 12 11
524262917
7 473906062
12 4 11 13 6 5 14
355582323
1 633497352
18
633497352
10 971821326
13 5 5 10 14 20 16 9 4 12
188083285
1 67560349
1
67560349
9 175070971
14 13 11 8 11 3 5 3 5
323903514
6 820579681
15 1 1 9 1 11
692700809
mod=1000000007
def powmod(a, b, mod):
    res = 1
    a %= mod
    assert b >= 0
    while b:
        if b & 1:
            res = res * a % mod
        a = a * a % mod
        b >>= 1
    return res
N = 10100
n, k = map(int, input().split())
poly = [0] * N
q = [0] * N
ret = [0] * N
a = list(map(int, input().split()))
ans = 0
poly[0] = 1
for i in range(n):
    for j in range(i, -1, -1):
        poly[j + 1] = (poly[j] + poly[j + 1]) % mod
        poly[j] = poly[j] * (mod - a[i]) % mod
for i in range(n):
    for j in range(n + 1):
        q[j] = poly[j]
    for j in range(n, 0, -1):
        ret[j - 1] = (ret[j - 1] + q[j]) % mod
        q[j - 1] = (q[j - 1] + q[j] * a[i]) % mod
coef = 1
for i in range(n):
    coef = coef * (k - i) % mod
    ans = (ans + powmod(n, mod - 2 - i, mod) * coef % mod * powmod(i + 1, mod - 2, mod) % mod * ret[i]) % mod
ans = ans * powmod(mod - 1, n + 1, mod) % mod
print(ans)# 1693218474.6046677