G. The Maximum Prefixtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou'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.InputEach 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.OutputFor 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}.ExampleInput
421 21 21 2 331 31 45 51 1 1 132 54 60 24 3 2 155 65 71 61 34 79 0 4 5 2 4Output
500000005 750000007 
1 1 1 
200000005 333333339 333333339 
500000005 880952391 801587311 781746041 789304620 
NoteIn 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.
421 21 21 2 331 31 45 51 1 1 132 54 60 24 3 2 155 65 71 61 34 79 0 4 5 2 4
500000005 750000007  1 1 1  200000005 333333339 333333339  500000005 880952391 801587311 781746041 789304620  
['dp', '*3200']