CF891E.Lust

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__i's such that 1 ≤ i ≤ n, but i ≠ x. Then, subtract a__x 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 . You have to find .

一个说谎的假见证者！

给你一个包含 $n$ 个整数的序列。初始时有一个变量 $res$，其值为 $0$。以下过程重复执行 $k$ 次：

• 在 $1$ 到 $n$ 中等概率随机选择一个下标，记为 $x$；
• 将所有满足 $1 \le i \le n$ 且 $i \ne x$ 的 $a_i$ 的乘积加到 $res$ 上；
• 将 $a_x$ 减 $1$。

你需要求出该过程结束时 $res$ 的期望值。可以证明：$res$ 的期望值可表示为一个既约分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 互质。你需要输出 $p \cdot q^{-1} \bmod 10^9+7$。

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 _a_1, _a_2, ..., a__n (0 ≤ a__i ≤ 109).

第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 5000$，$1 \leq k \leq 10^9$）—— 分别表示元素个数以及题目描述中指定的参数 $k$。

第二行包含 $n$ 个用空格分隔的整数 $a_1,\,a_2,\,...,\,a_n$（$0 \leq a_i \leq 10^9$）。

Output a single integer — the value .

输出一个整数——该值为 。