The Maximum Prefix

构造一个长度最多为 $n$ 的数组 $a$，其每个元素均为 $1$ 或 $-1$。生成方式如下： + 选择任意整数 $k\in[1,n]$ 作为 $a$ 的长度。 + 对于 $\forall i\in[1,k]$，有 $p_i$ 的概率设 $a_i=1$，有 $1-p_i$ 的概率设 $a_i=-1$。 在数列被生成后，计算 $s_i=a_1+a_2+a_3+...+a_i$。特别地，$s_0=0$。此时 $s$ 数组的最大前缀和 $S=max_{i=0}^ks_i$。 现在给定 $n+1$ 个正整数 $h_0,h_1,...,h_n$。$a$ 数组最大前缀和 $S$ 的分数为 $h_s$。现在，对于每个 $k$，你要求出一个数组长度为 $k$ 的期望分数对 $10^9+7$ 取模的结果。

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

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} < 10^9 + 7 $ , $ 1\le y_{i} < 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} < 10^9 + 7 $ ). It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 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 < M $ and $ 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

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