Tenzing 有一个长度为 $$$n$$$ 的数组 $$$a$$$ 和一个整数 $$$v$$$。
Tenzing 将执行以下操作 $$$m$$$ 次:
1. 随机选择一个整数$$$i$$$,使得$$$1 \leq i \leq n$$$ 一致。
2. 对于所有满足 $$$i \leq j \leq 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$$$ 的整数。换句话说,输出整数$$$x$$$,$$$0 \le x < M$$$ 和$$$x \cdot q \equiv p \pmod{M}$$$。
输入
输入的第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$v$$$ ($$$1\leq n\leq 5000$$$、$$$1\leq m,v\leq 10^9$$$)。
输入的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1\leq a_i\leq 10^9$$$)。
输出
输出 $$$\prod_{i=1}^n a_i$$$ 模 $$$10^9+7$$$ 的期望值。
示例
输入 #1
2 2 5 2 2
输出 #1
84
输入 #2
5 7 9 9 9 8 2 4
输出 #2
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$$$。