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 $ .

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.

For each test case output a single integer which is the probability that Alice will win modulo $ 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 $