← 返回题目列表

Codeforces · 891/E

E. 欲望

中文机器翻译题面 查看原题

说谎的假证人!

给定一个包含 n 个整数的序列。有一个变量 res 最初等于 0。以下过程重复 k 次。

从1到n中均匀随机选择一个索引。将其命名为 x。将所有 ai 的乘积添加到 res 中,使得 1 ≤ i ≤ n,但 i ≠ x。然后,将 ax 减 1。

您必须在过程结束时找到 res 的期望值。可以证明res的期望值可以表示为不可约分数$$\frac{p}{q}$$。你必须找到$$P \cdot Q^{-1} \bmod 1000000007$$。

输入

第一行包含两个整数 n 和 k (1 ≤ n ≤ 5000, 1 ≤ k ≤ 109) — 语句中指定的元素和参数 k 的数量。

第二行包含 n 个空格分隔的整数 a1, a2, ..., an (0 ≤ ai ≤ 109)。

输出

输出一个整数——值 $$P \cdot Q^{-1} \bmod 1000000007$$。

示例

输入 #1

2 1
5 5

输出 #1

5

输入 #2

1 10
80

输出 #2

10

输入 #3

2 2
0 0

输出 #3

500000003

输入#4

9 4
0 11 12 9 20 7 8 18 2

输出#4

169316356