G. Максимальный префикс
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы собираетесь сгенерировать массив $$$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$$$.

Входные данные

Каждый тест содержит несколько наборов входных данных. Первая строка содержит единственное целое число $$$t$$$ ($$$1 \le t \le 5000$$$) — количество наборов входных данных. Далее следует их описание.

Первая строка содержит целое число $$$n$$$ ($$$1\le n \le 5000$$$).

Затем в следующих $$$n$$$ строках содержатся по два целых числа $$$x_{i}$$$ и $$$y_{i}$$$ ($$$0 \le x_{i} < 10^9 + 7$$$, $$$1\le y_{i} < 10^9 + 7$$$, $$$x_{i} \le y_{i}$$$), которые определяют $$$p_{i} = \frac{x_{i}}{y_{i}}$$$.

Следующая строка содержит $$$n+1$$$ целое число $$$h_{0},h_{1}, \ldots, h_{n}$$$ ($$$0 \le h_{i} < 10^9 + 7$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$5000$$$.

Выходные данные

Для каждого набора входных данных выведите в одной строке $$$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}$$$.

Пример
Входные данные
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
Примечание

В первом наборе входных данных, если мы выберем $$$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$$$.