CF1842G.Tenzing and Random Operations

Yet another random problem.

Tenzing has an array $a$ of length $n$ and an integer $v$.

Tenzing will perform the following operation $m$ times:

1. Choose an integer $i$ such that $1 \leq i \leq n$ uniformly at random.
2. For all $j$ such that $i \leq j \leq n$, set $a_j := a_j + v$.

Tenzing wants to know the expected value of $\prod_{i=1}^n a_i$ after performing the $m$ operations, modulo $10^9+7$.

Formally, let $M = 10^9+7$. It can be shown that the answer can be expressed as an irreducible fraction $\frac{p}{q}$, where $p$ and $q$ are integers and $q \not \equiv 0 \pmod{M}$. Output the integer equal to $p \cdot q^{-1} \bmod M$. In other words, output the integer $x$ that $0 \le x \lt M$ and $x \cdot q \equiv p \pmod{M}$.

又一道随机问题。

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

丹增将执行以下操作 $m$ 次：

1. 均匀随机选择一个整数 $i$，满足 $1 \leq i \leq n$。
2. 对所有满足 $i \leq j \leq n$ 的 $j$，令 $a_j := a_j + v$。

丹增想知道：执行 $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$。

The first line of input contains three integers $n$, $m$ and $v$ ($1\leq n\leq 5000$, $1\leq m,v\leq 10^9$).

The second line of input contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1\leq a_i\leq 10^9$).

输入的第一行包含三个整数 $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$）。

Output the expected value of $\prod_{i=1}^n a_i$ modulo $10^9+7$.

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

There are three types of $a$ after performing all the $m$ operations :

1. $a_1=2,a_2=12$ with $\frac{1}{4}$ probability.

2. $a_1=a_2=12$ with $\frac{1}{4}$ probability.

3. $a_1=7,a_2=12$ with $\frac{1}{2}$ probability.

So the expected value of $a_1\cdot a_2$ is $\frac{1}{4}\cdot (24+144) + \frac{1}{2}\cdot 84=84$.

执行全部 $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.$$