说谎的假证人!
给定一个包含 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