CF1810G.The Maximum Prefix

You're going to generate an array $a$ with a length of at most $n$, where each $a_{i}$ equals either $1$ or $-1$.

You generate this array in the following way.

• First, you choose some integer $k$ ($1\le k \le n$), which decides the length of $a$.
• Then, for each $i$ ($1\le i \le k$), you set $a_{i} = 1$ with probability $p_{i}$, otherwise set $a_{i} = -1$ (with probability $1 - p_{i}$).

After the array is generated, you calculate $s_{i} = a_{1} + a_{2} + a_{3}+ \ldots + a_{i}$. Specially, $s_{0} = 0$. Then you let $S$ equal to $\displaystyle \max_{i=0}^{k}{s_{i}}$. That is, $S$ is the maximum prefix sum of the array $a$.

You are given $n+1$ integers $h_{0} , h_{1}, \ldots ,h_{n}$. The score of an array $a$ with maximum prefix sum $S$ is $h_{S}$. Now, for each $k$, you want to know the expected score for an array of length $k$ modulo $10^9+7$.

你将生成一个长度至多为 $n$ 的数组 $a$，其中每个元素 $a_{i}$ 的值为 $1$ 或 $-1$。

该数组按如下方式生成：

• 首先，你选择某个整数 $k$（满足 $1\le k \le n$），它决定数组 $a$ 的长度；
• 然后，对每个 $i$（满足 $1\le i \le k$），以概率 $p_{i}$ 令 $a_{i} = 1$，否则以概率 $1 - p_{i}$ 令 $a_{i} = -1$。

数组生成完毕后，你计算前缀和 $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$ 取模）。

Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 5000$) — the number of test cases. Their description follows.

The first line contains an integer $n$ ($1\le n \le 5000$).

Then for the following $n$ lines, each line contains two integers $x_{i}$ and $y_{i}$ ($0 \le x_{i} \lt 10^9 + 7$, $1\le y_{i} \lt 10^9 + 7$, $x_{i} \le y_{i}$), indicating $p_{i} = \frac{x_{i}}{y_{i}}$.

The next line contains $n+1$ integers $h_{0},h_{1}, \ldots, h_{n}$ ($0 \le h_{i} \lt 10^9 + 7$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $5000$.

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 5000$），表示测试用例的数量。随后是这些测试用例的描述。

第一行包含一个整数 $n$（$1\le n \le 5000$）。

接下来的 $n$ 行中，每行包含两个整数 $x_{i}$ 和 $y_{i}$（$0 \le x_{i} \lt 10^9 + 7$，$1\le y_{i} \lt 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} \lt 10^9 + 7$）。

保证所有测试用例中 $n$ 的总和不超过 $5000$。

For each test case, output $n$ integers in one single line, the $i$-th of which denotes the expected score for an array of length $i$, 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 such an integer $x$ that $0 \le x \lt M$ and $x \cdot q \equiv p \pmod{M}$.

对每个测试用例，在一行中输出 $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$ 的整数。换言之，输出满足 $0 \le x \lt M$ 且 $x \cdot q \equiv p \pmod{M}$ 的整数 $x$。

In the first test case, if we choose $k=1$, there are $2$ possible arrays with equal probabilities: $[1]$ and $[-1]$. The $S$ values for them are $1$ and $0$. So the expected score is $\frac{1}{2}h_{0} + \frac{1}{2}h_{1} = \frac{3}{2}$. If we choose $k=2$, there are $4$ possible arrays with equal probabilities: $[1,1]$, $[1,-1]$, $[-1,1]$, $[-1,-1]$, and the $S$ values for them are $2,1,0,0$. So the expected score is $\frac{1}{2}h_{0} + \frac{1}{4}h_{1} + \frac{1}{4}h_{2} = \frac{7}{4}$.

In the second test case, no matter what the $S$ value is, the score is always $1$, so the expected score is always $1$.

在第一个测试用例中，若选择 $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$。