G. Tenzing 与随机操作

每个测试的时间限制：$2$ 秒
内存限制：$1024$ 兆字节

又一道随机问题。

Tenzing 有一个长度为 $n$ 的数组 $a$ 和一个整数 $v$。

Tenzing 将执行以下操作 $m$ 次：

• 均匀随机地选择一个下标 $i$，满足 $1 \le i \le n$。
• 对于所有满足 $i \le j \le n$ 的 $j$，令 $a_j := a_j + v$。

Tenzing 想知道执行完 $m$ 次操作后，$\prod_{i=1}^n a_i$ 的期望值，结果对 $10^9+7$ 取模。

形式化地，令 $M = 10^9+7$。可以证明答案可以表示为不可约分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 是整数，且 $q \not\equiv 0 \pmod{M}$。输出等于 $p \cdot q^{-1} \bmod M$ 的整数。换句话说，输出满足 $0 \le x < M$ 且 $x \cdot q \equiv p \pmod{M}$ 的整数 $x$。

输入

第一行包含三个整数 $n$，$m$ 和 $v$ ($1 \le n \le 5000$，$1 \le m, v \le 10^9$)。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$)。

输出

输出 $\prod_{i=1}^n a_i$ 的期望值，对 $10^9+7$ 取模。

样例

输入：

2 2 5
2 2

输出：

84

输入：

5 7 9
9 9 8 2 4

输出：

975544726

提示

执行完所有 $m$ 次操作后，数组 $a$ 有三种可能：

1. $a_1 = 2$，$a_2 = 12$，概率为 $\frac{1}{4}$。
2. $a_1 = a_2 = 12$，概率为 $\frac{1}{4}$。
3. $a_1 = 7$，$a_2 = 12$，概率为 $\frac{1}{2}$。

因此 $a_1 \cdot a_2$ 的期望值为 $\frac{1}{4} \cdot (24 + 144) + \frac{1}{2} \cdot 84 = 84$。