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

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

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