CF2192F.Fish Fight

In a pond, $n$ fish are in a line. For each fish $i$, its size is $a_i$, and any fish that eats it grows by $b_i$.

Alice picks fish $x$, Bob picks fish $y$. They alternate turns, starting with Alice's fish. On each player's turn, let their fish have size $p$. The fish will eat an adjacent fish with size $q$ that satisfies $p \geq q$. If more than one such fish exists, it chooses uniformly at random among them. Eating increases its size by the eaten fish's $b_i$.

If, at the start of its turn, a fish cannot eat any adjacent fish, it is instead eaten by its neighbours (A fish at an endpoint has one neighbour; a fish in the interior has two). If Alice's fish is eaten (either by Bob's fish or by her neighboring fishes), she immediately loses. Similarly, if Bob's fish is eaten (either by Alice's fish or by his neighboring fishes), he immediately loses.

Given Alice's and Bob's chosen fishes, compute the probability that Alice wins, modulo $10^9+7$.

More formally, let $M=10^9+7$. The answer can be written as an irreducible fraction $\frac{p}{q}$ with $q \not\equiv 0 \pmod M$. Output $p \, q^{-1} \bmod M$, the unique integer $x$ with $0 \le x \lt M$ and $x q \equiv p \pmod M$.

一个池塘中有 $n$ 条鱼排成一行。对于第 $i$ 条鱼，其大小为 $a_i$，且任何吃掉它的鱼的大小将增加 $b_i$。

爱丽丝选择第 $x$ 条鱼，鲍勃选择第 $y$ 条鱼。他们轮流行动，由爱丽丝的鱼先行开始。在每位玩家的回合中，设其鱼当前大小为 $p$。该鱼将吃掉一个相邻的、大小为 $q$ 且满足 $p \geq q$ 的鱼。若存在多个满足条件的相邻鱼，则等概率地随机选择其中一个。吃掉一条鱼后，该鱼的大小增加被吃鱼对应的 $b_i$ 值。

若在某条鱼的回合开始时，它无法吃掉任何相邻的鱼，则它反而会被其邻鱼吃掉（位于行首或行尾的鱼只有一个邻鱼；位于中间的鱼有两个邻鱼）。若爱丽丝的鱼被吃掉（无论是被鲍勃的鱼吃掉，还是被其邻鱼吃掉），她立即失败。类似地，若鲍勃的鱼被吃掉（无论是被爱丽丝的鱼吃掉，还是被其邻鱼吃掉），他立即失败。

给定爱丽丝与鲍勃所选的鱼，计算爱丽丝获胜的概率，结果对 $10^9+7$ 取模。

更严格地说，令 $M = 10^9 + 7$。答案可表示为最简分数 $\frac{p}{q}$，其中 $q \not\equiv 0 \pmod{M}$。请输出 $p \, q^{-1} \bmod M$，即唯一满足 $0 \le x < M$ 且 $x q \equiv p \pmod{M}$ 的整数 $x$。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$). The description of the test cases follows.

The first line of each testcase contains a single integer $n$ ($2 \le n \le 3000$) — the number of fish in pond.

The second line contains two integers $x$ and $y$ ($1 \le x,y \le n$; $x \neq y$).

The third line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$).

The fourth line contains $n$ integers $b_1, b_2, \ldots, b_n$ ($0 \le b_i \le 10^9$).

It is guaranteed that the sum of $n$ does not exceed $3000$ over all test cases.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case output a single integer which is the probability that Alice will win modulo $10^9 + 7$.

对于每个测试用例，输出一个整数，表示 Alice 获胜的概率对 $10^9 + 7$ 取模的结果。

In the first test case, Alice's fish can't eat any of the adjacent fish, hence Alice always loses.

In the second test case, Alice's fish has only one adjacent fish, which is Bob's fish, Since Alice's fish size is greater than or equal to Bob's fish size, Alice always wins.

In the third test case, in the first turn, Alice's fish can eat both the adjacent fish.

Case $1$: It eats fish $3$ (Bob's fish). Alice wins.

Case $2$: It eats fish $1$. The new size of Alice's fish will be $a_2 + b_1 = 4 + 0 = 4$. This will lead to Bob's fish always eating Alice's fish in the second turn. Alice loses.

Both cases are equally likely, hence the probability of Alice winning is $0.5$

In the fourth test case, the probability of Alice winning is $0.75$

在第一个测试用例中，Alice 的鱼无法吃掉任何相邻的鱼，因此 Alice 总是输。

在第二个测试用例中，Alice 的鱼仅有一个相邻的鱼，即 Bob 的鱼。由于 Alice 的鱼的尺寸大于或等于 Bob 的鱼的尺寸，Alice 总是赢。

在第三个测试用例中，在第一回合，Alice 的鱼可以吃掉两个相邻的鱼。

情况 $1$：它吃掉鱼 $3$（Bob 的鱼）。Alice 获胜。

情况 $2$：它吃掉鱼 $1$。Alice 的鱼的新尺寸将为 $a_2 + b_1 = 4 + 0 = 4$。这将导致 Bob 的鱼在第二回合总是吃掉 Alice 的鱼。Alice 输。

两种情况出现的可能性相等，因此 Alice 获胜的概率为 $0.5$。

在第四个测试用例中，Alice 获胜的概率为 $0.75$。