题目描述

Y 同学有一个长度为 $n$ 的非负整数序列 $a_1,a_2,\dots,a_n$，以及一个初始为 $0$ 的变量 $res$。接下来会独立重复 $k$ 次操作：每次等概率选择一个下标 $x$，先把所有 $i\ne x$ 的 $a_i$ 的乘积加到 $res$ 上，然后令 $a_x$ 减少 $1$。

注意某些 $a_i$ 在操作过程中可能变成负数，乘积仍按普通整数乘法理解。Y 同学关心所有随机选择下 $res$ 的期望值。

可以证明该期望能写成最简分数 $P/Q$，且 $Q$ 在模 $10^9+7$ 意义下可逆。请输出 $P\cdot Q^{-1}$ 对 $10^9+7$ 取模的值。

输入格式

第一行包含两个整数 $n,k$。

第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$。

输出格式

输出一行一个整数，表示期望值在模 $10^9+7$ 意义下的值。

样例

样例输入 #1

2 1
2 3

样例输出 #1

500000006

数据范围与约定

对于 $100\%$ 的数据，保证 $1\le n\le5000$，$1\le k\le10^9$，$0\le a_i\le10^9$。

特殊性质 A：保证 $k\le n$。 特殊性质 B：保证存在 $a_i=0$。