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$$$.
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$$$.
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}$$$.
import math
mod = int(1000000000.0 + 7)

def fpow(a, b):
    ans = 1
    while b:
        if b & 1:
            ans = ans * a % mod
        a = a * a % mod
        b >>= 1
    return ans
t = int(input())
for _ in range(t):
    n = int(input())
    p_arr = [0] * n
    q_arr = [0] * n
    for i in range(n):
        (x, y) = map(int, input().split())
        p = x * fpow(y, mod - 2) % mod
        p_arr[i] = p
        q_arr[i] = (1 - p_arr[i] + mod) % mod
    h_arr = list(map(int, input().split()))
    sol = [[0] * (n + 1), [0] * (n + 1)]
    sol[0] = h_arr
    result = [0] * n
    for i in range(1, n + 1):
        sol[1] = [(p_arr[i - 1] * sol[0][j + 1] + q_arr[i - 1] * sol[0][max(0, j - 1)]) % mod for j in range(n)] + [q_arr[i - 1] * sol[0][n] % mod]
        sol[0] = [e for e in sol[1]]
        result[i - 1] = sol[1][0]
    print(*result)
mod = int(1000000000.0 + 7)

def binPow(b, e):
    r = 1
    while e:
        if e % 2 == 1:
            r = r * b % mod
        b = b * b % mod
        e = e // 2
    return int(r)

def P(s):
    (x, y) = [v for v in map(int, s.split(' '))]
    return x * binPow(y, mod - 2) % mod

def solve():
    n = int(input())
    p = [P(input()) for i in range(n)]
    h = [x for x in map(int, input().split())]
    dp = [[0] * (n + 4) for i in range(n + 2)]
    for j in range(n + 1):
        dp[0][j] = h[j]
    for i in range(1, n + 1):
        for j in range(n + 1):
            dp[i][j] = (p[i - 1] * dp[i - 1][j + 1] + (1 - p[i - 1]) % mod * dp[i - 1][max(j - 1, 0)]) % mod
    for k in range(1, n + 1):
        print(dp[k][0], end=' ')
    print('')
t = int(input())
for _ in range(t):
    solve()
mod = int(1000000000.0 + 7)

def binPow(b, e):
    r = 1
    while e:
        if e % 2 == 1:
            r = r * b % mod
        b = b * b % mod
        e = e // 2
    return int(r)

def P(s):
    (x, y) = [v for v in map(int, s.split(' '))]
    return x * binPow(y, mod - 2) % mod

def Caso():
    n = int(input())
    p = [P(input()) for i in range(n)]
    h = [x for x in map(int, input().split())]
    dp = [[0] * (n + 4) for i in range(n + 2)]
    for j in range(n + 1):
        dp[0][j] = h[j]
    for i in range(1, n + 1):
        for j in range(n + 1):
            dp[i][j] = (p[i - 1] * dp[i - 1][j + 1] + (1 - p[i - 1]) % mod * dp[i - 1][max(j - 1, 0)]) % mod
    for k in range(1, n + 1):
        print(dp[k][0], end=' ')
    print('')
t = int(input())
for _ in range(t):
    Caso()