在一个池塘里,$$$n$$$ 条鱼排成一排。对于每条鱼 $$$i$$$,其大小为 $$$a_i$$$,任何吃掉它的鱼都会增长 $$$b_i$$$。
Alice 挑鱼 $$$x$$$,Bob 挑鱼 $$$y$$$。他们轮流从爱丽丝的鱼开始。在每个玩家的回合中,让他们的鱼的大小为 $$$p$$$。该鱼将吃掉大小为 $$$q$$$ 且满足 $$$p \geq q$$$ 的相邻鱼。如果存在不止一条这样的鱼,它会在其中均匀随机选择。吃东西会增加其体积 吃过 鱼的$$$b_i$$$。
如果在回合开始时,一条鱼不能吃掉任何相邻的鱼,它就会被其邻居吃掉(端点处的鱼有一个邻居;内部的鱼有两个)。如果爱丽丝的鱼被吃掉了(要么被鲍勃的鱼吃掉,要么被她邻近的鱼吃掉),她立即就输了。同样,如果鲍勃的鱼被吃掉(无论是被爱丽丝的鱼还是被他邻近的鱼吃掉),他就会立即失败。
给定 Alice 和 Bob 选择的鱼,计算 Alice 获胜的概率,以 $$$10^9+7$$$ 为模。
更正式地说,令$$$M=10^9+7$$$。答案可以写成不可约分数 $$$\frac{p}{q}$$$ 其中 $$$q \not\equiv 0 \pmod M$$$。输出$$$p \, q^{-1} \bmod M$$$,唯一整数$$$x$$$,其中$$$0 \le x \lt M$$$ 和$$$x q \equiv p \pmod M$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 500$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 3000$$$) — 池塘中鱼的数量。
第二行包含两个整数 $$$x$$$ 和 $$$y$$$ ($$$1 \le x,y \le n$$$; $$$x \neq y$$$)。
第三行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$)。
第四行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \le b_i \le 10^9$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$3000$$$。
输出
对于每个测试用例,输出一个整数,即 Alice 获胜的概率以 $$$10^9 + 7$$$ 为模。
示例
输入复制
621 21 21 121 22 11 132 31 4 40 1 154 22 6 5 5 31 2 1 3 273 51 1 1 1 1 1 10 0 0 0 0 0 1108 32 5 9 3 8 4 5 6 2 71 3 5 2 7 3 4 2 2 3
输出复制
01500000004750000006375000003687500005
注意
在第一个测试用例中,爱丽丝的鱼不能吃任何相邻的鱼,因此爱丽丝总是输。
在第二个测试用例中,Alice 的鱼只有一条相邻的鱼,即 Bob 的鱼,由于 Alice 的鱼大小大于或等于 Bob 的鱼大小,Alice 总是获胜。
在第三个测试用例中,在第一个回合中,爱丽丝的鱼可以吃掉相邻的鱼。
案例$$$1$$$:它吃鱼$$$3$$$(鲍勃的鱼)。爱丽丝赢了。
案例$$$2$$$:它吃鱼$$$1$$$。 Alice 的鱼的新大小将为 $$$a_2 + b_1 = 4 + 0 = 4$$$。这会导致鲍勃的鱼在第二回合总是吃掉爱丽丝的鱼。爱丽丝输了。
两种情况的可能性相同,因此 Alice 获胜的概率为 $$$0.5$$$
在第四个测试用例中,Alice 获胜的概率为 $$$0.75$$$