F. Рыбная битва
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В пруду находится $$$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$$$ — единственное целое число $$$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$$$ по всем наборам входных данных.

Выходные данные

Для каждого набора входных данных выведите одно целое число — вероятность того, что Алиса выиграет, по модулю $$$10^9 + 7$$$.

Пример
Входные данные
6
2
1 2
1 2
1 1
2
1 2
2 1
1 1
3
2 3
1 4 4
0 1 1
5
4 2
2 6 5 5 3
1 2 1 3 2
7
3 5
1 1 1 1 1 1 1
0 0 0 0 0 0 1
10
8 3
2 5 9 3 8 4 5 6 2 7
1 3 5 2 7 3 4 2 2 3
Выходные данные
0
1
500000004
750000006
375000003
687500005
Примечание

В первом наборе входных данных рыба Алисы не может съесть ни одну из соседних рыб, следовательно, Алиса всегда проигрывает.

Во втором наборе входных данных у рыбы Алисы есть только одна соседняя рыба, которой является рыба Боба. Поскольку размер рыбы Алисы больше или равен размеру рыбы Боба, Алиса всегда выигрывает.

В третьем наборе входных данных на первом ходе рыба Алисы может съесть обе соседние рыбы.

Случай $$$1$$$: Она съедает рыбу $$$3$$$ (рыба Боба). Алиса выигрывает.

Случай $$$2$$$: Она съедает рыбу $$$1$$$. Новый размер рыбы Алисы будет $$$a_2 + b_1 = 4 + 0 = 4$$$. Это приведёт к тому, что рыба Боба всегда съест рыбу Алисы на втором ходе. Алиса проигрывает.

Оба случая равновероятны, следовательно, вероятность выигрыша Алисы составляет $$$0.5$$$.

В четвёртом наборе входных данных вероятность выигрыша Алисы составляет $$$0.75$$$.