您将生成一个长度最多为 $$$n$$$ 的数组 $$$a$$$,其中每个 $$$a_{i}$$$ 等于 $$$1$$$ 或 $$$-1$$$。
您可以通过以下方式生成此数组。
- 首先,选择一些整数 $$$k$$$ ($$$1\le k \le n$$$),它决定 $$$a$$$ 的长度。
- 然后,对于每个 $$$i$$$ ($$$1\le i \le k$$$),您设置 $$$a_{i} = 1$$$,概率为 $$$p_{i}$$$,否则设置 $$$a_{i} = -1$$$(概率为 $$$1 - p_{i}$$$)。
生成数组后,计算 $$$s_{i} = a_{1} + a_{2} + a_{3}+ \ldots + a_{i}$$$。特别是,$$$s_{0} = 0$$$。然后让 $$$S$$$ 等于 $$$\displaystyle \max_{i=0}^{k}{s_{i}}$$$。即$$$S$$$是数组$$$a$$$的最大前缀和。
给你 $$$n+1$$$ 整数 $$$h_{0} , h_{1}, \ldots ,h_{n}$$$。具有最大前缀和 $$$S$$$ 的数组 $$$a$$$ 的分数为 $$$h_{S}$$$。现在,对于每个 $$$k$$$,您想知道长度为 $$$k$$$ 模 $$$10^9+7$$$ 的数组的预期分数。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 5000$$$) — 测试用例的数量。他们的描述如下。
第一行包含一个整数 $$$n$$$ ($$$1\le n \le 5000$$$)。
那么对于下面的 $$$n$$$ 行,每行包含两个整数 $$$x_{i}$$$ 和 $$$y_{i}$$$ ($$$0 \le x_{i} < 10^9 + 7$$$, $$$1\le y_{i} < 10^9 + 7$$$, $$$x_{i} \le y_{i}$$$),表示$$$p_{i} = \frac{x_{i}}{y_{i}}$$$。
下一行包含 $$$n+1$$$ 整数 $$$h_{0},h_{1}, \ldots, h_{n}$$$ ($$$0 \le h_{i} < 10^9 + 7$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$5000$$$。
输出
对于每个测试用例,在一行中输出 $$$n$$$ 个整数,其中第 $$$i$$$ 表示长度为 $$$i$$$ 的数组的预期得分,以 $$$10^9 + 7$$$ 为模。
正式地,让 $$$M = 10^9 + 7$$$。可以证明,答案可以表示为不可约分数 $$$\frac{p}{q}$$$,其中 $$$p$$$ 和 $$$q$$$ 是整数,$$$q \not \equiv 0 \pmod{M}$$$。输出等于 $$$p \cdot q^{-1} \bmod M$$$ 的整数。换句话说,输出一个整数$$$x$$$,使得$$$0 \le x < M$$$ 且$$$x \cdot q \equiv p \pmod{M}$$$。
示例
输入 #1
4 2 1 2 1 2 1 2 3 3 1 3 1 4 5 5 1 1 1 1 3 2 5 4 6 0 2 4 3 2 1 5 5 6 5 7 1 6 1 3 4 7 9 0 4 5 2 4
输出 #1
500000005 750000007 1 1 1 200000005 333333339 333333339 500000005 880952391 801587311 781746041 789304620
注意
在第一个测试用例中,如果我们选择 $$$k=1$$$,则存在 $$$2$$$ 个具有相同概率的可能数组:$$$[1]$$$ 和 $$$[-1]$$$。它们的 $$$S$$$ 值为 $$$1$$$ 和 $$$0$$$。因此预期得分为 $$$\frac{1}{2}h_{0} + \frac{1}{2}h_{1} = \frac{3}{2}$$$。如果我们选择 $$$k=2$$$,则存在 $$$4$$$ 个具有相同概率的可能数组:$$$[1,1]$$$、$$$[1,-1]$$$、$$$[-1,1]$$$、$$$[-1,-1]$$$,并且它们的 $$$S$$$ 值为 $$$2,1,0,0$$$。因此预期得分为 $$$\frac{1}{2}h_{0} + \frac{1}{4}h_{1} + \frac{1}{4}h_{2} = \frac{7}{4}$$$。
在第二个测试用例中,无论 $$$S$$$ 值是什么,分数始终为 $$$1$$$,因此预期分数始终为 $$$1$$$。