A16017. 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 < M$ and $x \cdot q \equiv p \pmod{M}$ .

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$ ).

Output the expected value of $\prod_{i=1}^n a_i$ modulo $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$ .