write a go solution for Description:
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<=k<=n), which decides the length of a.
- Then, for each i (1<=i<=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 displaystylemax_i=0^ks_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.

Input Format:
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=fracx_iy_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.

Output Format:
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 p/q, where p and q are integers and qnotequiv0pmodM. Output the integer equal to p*q^-1bmodM. In other words, output such an integer x that 0<=x<M and x*qequivppmodM.

Note:
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 1/2h_0+1/2h_1=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 1/2h_0+1/4h_1+1/4h_2=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.. Output only the code with no comments, explanation, or additional text.