G. Тенцинг и случайные операции
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод
Еще одна задача про случайность.

У Тенцинга есть массив $$$a$$$ длины $$$n$$$ и целое число $$$v$$$.

Тенцинг выполняет следующую операцию $$$m$$$ раз:

  1. Выбрать целое число $$$i$$$ такое, что $$$1 \leq i \leq n$$$, равномерно случайным образом.
  2. Для всех $$$j$$$ таких, что $$$i \leq j \leq n$$$, присвоить $$$a_j := a_j + v$$$.

Тенцинг хочет узнать ожидаемое значение $$$\prod_{i=1}^n a_i$$$ после выполнения $$$m$$$ операций, по модулю $$$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$$$.

Примеры
Входные данные
2 2 5
2 2
Выходные данные
84
Входные данные
5 7 9
9 9 8 2 4
Выходные данные
975544726
Примечание

Существует три возможных значения $$$a$$$ после выполнения всех $$$m$$$ операций:

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