Еще одна задача про случайность.
У Тенцинга есть массив \(a\) длины \(n\) и целое число \(v\).
Тенцинг выполняет следующую операцию \(m\) раз:
- Выбрать целое число \(i\) такое, что \(1 \leq i \leq n\), равномерно случайным образом.
- Для всех \(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}\).
Выходные данные
Выведите ожидаемое значение \(\prod_{i=1}^n a_i\) по модулю \(10^9+7\).
Примечание
Существует три возможных значения \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 2 5
2 2
|
84
|
|
2
|
5 7 9
9 9 8 2 4
|
975544726
|