D. Допустимые битонические перестановки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано пять целых чисел $$$n$$$, $$$i$$$, $$$j$$$, $$$x$$$, и $$$y$$$. Найдите количество битонических перестановок $$$B$$$, чисел от $$$1$$$ до $$$n$$$, таких, что $$$B_i=x$$$, и $$$B_j=y$$$. Так как ответ может быть очень большим, выведите его по модулю $$$10^9+7$$$.

Битоническая перестановка — это перестановка чисел, такая, что элементы перестановки сначала увеличиваются до определенного индекса $$$k$$$, $$$2 \le k \le n-1$$$, а затем уменьшайте до конца. Обратитесь к примечаниям для получения дополнительных разъяснений.

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

В первой строке содержится одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) —количество наборов входных данных.

В единственной строке набора входных данных содержатся целые числа, $$$n$$$, $$$i$$$, $$$j$$$, $$$x$$$, и $$$y$$$ ($$$3 \le n \le 100$$$ и $$$1 \le i,j,x,y \le n$$$).

Гарантируется, что $$$i < j$$$ и $$$x \ne y$$$.

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

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

Пример
Входные данные
7
3 1 3 2 3
3 2 3 3 2
4 3 4 3 1
5 2 5 2 4
5 3 4 5 4
9 3 7 8 6
20 6 15 8 17
Выходные данные
0
1
1
1
3
0
4788
Примечание

Перестановка — это массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в любом порядке. Например, $$$[2,3,1,5,4]$$$ это перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но $$$4$$$ встречается в массиве).

Массив из $$$n \ge 3$$$ элементов битонический, если его элементы сначала увеличиваются до индекса $$$k$$$, $$$2 \le k \le n-1$$$, а затем уменьшается до конца. Например, $$$[2,5,8,6,1]$$$ это битонический массив с $$$k=3$$$, но $$$[2,5,8,1,6]$$$ не битонический массив (элементы сначала возрастают до $$$k=3$$$, затем убывают, а затем возрастают снова).

Битоническая перестановка — это перестановка, в которой элементы следуют вышеупомянутому битоническому свойству. Например, $$$[2,3,5,4,1]$$$ является битонической перестановкой, но $$$[2,3,5,1,4]$$$ не является битонической перестановкой (поскольку это не битонический массив) и $$$[2,3,4,4,1]$$$также не является битонической перестановкой (поскольку это не перестановка).

Объяснение примера из условий

Для $$$n=3$$$, возможные перестановки это $$$[1,2,3]$$$, $$$[1,3,2]$$$, $$$[2,1,3]$$$, $$$[2,3,1]$$$, $$$[3,1,2]$$$, и $$$[3,2,1]$$$. Среди приведенных перестановок битоническими перестановками являются $$$[1,3,2]$$$ и $$$[2,3,1]$$$.

В первом тестовом примере ожидаемая перестановка должна иметь вид $$$[2,?,3]$$$, который не удовлетворяет ни одной из двух битонических перестановок с $$$n=3$$$, следовательно, ответ равен 0.

Во втором тестовом примере ожидаемая перестановка должна иметь вид $$$[?,3,2]$$$, который удовлетворяет только битонической перестановке $$$[1,3,2]$$$, следовательно, ответ 1.