Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

combinatorics

dp

math

probabilities

*2800

No tag edit access

The problem statement has recently been changed. View the changes.

×
G. Tenzing and Random Operations

time limit per test

2 secondsmemory limit per test

1024 megabytesinput

standard inputoutput

standard outputYet another random problem.

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

Tenzing will perform the following operation $$$m$$$ times:

- Choose an integer $$$i$$$ such that $$$1 \leq i \leq n$$$ uniformly at random.
- 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}$$$.

Input

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

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

Examples

Input

2 2 5 2 2

Output

84

Input

5 7 9 9 9 8 2 4

Output

975544726

Note

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

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/25/2024 05:10:48 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|