Вы собираетесь сгенерировать массив \(a\) длиной не более \(n\), где каждый элемент \(a_{i}\) равен либо \(1\), либо \(-1\).
Вы генерируете этот массив следующим способом.
- Сначала вы выбираете некоторое \(k\) (\(1\le k \le n\)), которое определяет длину \(a\).
- Далее для каждого \(i\) (\(1\le i \le k\)) вы устанавливаете \(a_{i} = 1\) с вероятностью \(p_{i}\), в противном случае вы устанавливаете \(a_{i} = -1\) (с вероятностью \(1 - p_{i}\)).
После того, как массив сгенерирован, вы вычисляете \(s_{i} = a_{1} + a_{2} + a_{3}+ \ldots + a_{i}\). Отдельно положим \(s_{0} = 0\). Затем вы вычисляете \(S\) как \(\displaystyle \max_{i=0}^{k}{s_{i}}\). То есть \(S\) — это максимальная префиксная сумма массива \(a\).
Вам дано \(n+1\) целое число \(h_{0} , h_{1}, \ldots ,h_{n}\). Оценка массива \(a\) с максимальной суммой префиксов \(S\) равна \(h_{S}\). Теперь для каждого \(k\) вы хотите узнать математическое ожидание оценки для массива длины \(k\) по модулю \(10^9+7\).
Выходные данные
Для каждого набора входных данных выведите в одной строке \(n\) целых чисел, \(i\)-е из которых обозначает ожидаемый результат для массива длины \(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\). Другими словами, выведите такое целое число \(x\), что \(0 \le x < M\) и \(x \cdot q \equiv p \pmod{M}\).
Примечание
В первом наборе входных данных, если мы выберем \(k=1\), будет \(2\) возможных массива с равными вероятностями: \([1]\) и \([-1]\). Значения \(S\) для них составляют \(1\) и \(0\). Таким образом, ожидаемый результат равен \(\frac{1}{2}h_{0} + \frac{1}{2}h_{1} = \frac{3}{2}\). Если мы выберем \(k=2\), будет \(4\) возможных массива с равными вероятностями: \([1,1]\), \([1,-1]\), \([-1,1]\), \([-1,-1]\), и значения \(S\) для них равны \(2,1,0,0\). Таким образом, ожидаемый результат равен \(\frac{1}{2}h_{0} + \frac{1}{4}h_{1} + \frac{1}{4}h_{2} = \frac{7}{4}\).
Во втором наборе входных данных, независимо от значения \(S\), оценка всегда равна \(1\), поэтому ожидаемая оценка всегда равна \(1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2
1 2
1 2
1 2 3
3
1 3
1 4
5 5
1 1 1 1
3
2 5
4 6
0 2
4 3 2 1
5
5 6
5 7
1 6
1 3
4 7
9 0 4 5 2 4
|
500000005 750000007
1 1 1
200000005 333333339 333333339
500000005 880952391 801587311 781746041 789304620
|