B"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. 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 <= t <= 5000 ) -- the number of test cases. Their description follows. The first line contains an integer n ( 1 <= n <= 5000 ). Then for the following n lines, each line contains two integers x_{i} and y_{i} ( 0 <= x_{i} < 10^9 + 7 , 1 <= y_{i} < 10^9 + 7 , x_{i} <= 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 <= 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 <= 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 wi"...