← 返回题目列表

Codeforces · 1842/G

G. Tenzing 和随机操作

中文机器翻译题面 查看原题

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$$$。