Valid Bitonic Permutations

给定一个长度为 $n$ 的数列 $a_1, a_2, \ldots, a_n$，如果它满足如下两个条件，则我们称它是一个双调排列： 1. 这个数列是一个 $1 \sim n$ 的排列（也就是说对于任意一个整数 $1 \le i \le n$，数列中都存在一个等于 $i$ 的元素） 2. 存在一个下标 $k(2 \le k \le n-1)$，使得 $a_1$ 到 $a_k$ 是单调递增的，$a_k$ 到 $a_n$ 是单调递减的。 现在给你五个整数 $n, i, j, x, y$，它们表示数列长度为 $n$，$a_i = x$，$a_j = y$，求满足该条件的双调排列的个数。 由于满足条件的双调排列数可能很大，所以你只需要输出排列数模 $10^9 + 7$ 的结果即可。

You are given five integers $ n $ , $ i $ , $ j $ , $ x $ , and $ y $ . Find the number of bitonic permutations $ B $ , of the numbers $ 1 $ to $ n $ , such that $ B_i=x $ , and $ B_j=y $ . Since the answer can be large, compute it modulo $ 10^9+7 $ . A bitonic permutation is a permutation of numbers, such that the elements of the permutation first increase till a certain index $ k $ , $ 2 \le k \le n-1 $ , and then decrease till the end. Refer to notes for further clarification.

Each test contains multiple test cases. The first line contains a single integer $ t $ ( $ 1 \le t \le 100 $ ) — the number of test cases. The description of test cases follows. The only line of each test case contains five integers, $ n $ , $ i $ , $ j $ , $ x $ , and $ y $ ( $ 3 \le n \le 100 $ and $ 1 \le i,j,x,y \le n $ ). It is guaranteed that $ i < j $ and $ x \ne y $ .

For each test case, output a single line containing the number of bitonic permutations satisfying the above conditions modulo $ 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

A permutation is an array consisting of $ n $ distinct integers from $ 1 $ to $ n $ in arbitrary order. For example, $ [2,3,1,5,4] $ is a permutation, but $ [1,2,2] $ is not a permutation ( $ 2 $ appears twice in the array) and $ [1,3,4] $ is also not a permutation ( $ n=3 $ but there is $ 4 $ in the array). An array of $ n \ge 3 $ elements is bitonic if its elements are first increasing till an index $ k $ , $ 2 \le k \le n-1 $ , and then decreasing till the end. For example, $ [2,5,8,6,1] $ is a bitonic array with $ k=3 $ , but $ [2,5,8,1,6] $ is not a bitonic array (elements first increase till $ k=3 $ , then decrease, and then increase again). A bitonic permutation is a permutation in which the elements follow the above-mentioned bitonic property. For example, $ [2,3,5,4,1] $ is a bitonic permutation, but $ [2,3,5,1,4] $ is not a bitonic permutation (since it is not a bitonic array) and $ [2,3,4,4,1] $ is also not a bitonic permutation (since it is not a permutation). Sample Test Case Description For $ n=3 $ , possible permutations are $ [1,2,3] $ , $ [1,3,2] $ , $ [2,1,3] $ , $ [2,3,1] $ , $ [3,1,2] $ , and $ [3,2,1] $ . Among the given permutations, the bitonic permutations are $ [1,3,2] $ and $ [2,3,1] $ . In the first test case, the expected permutation must be of the form $ [2,?,3] $ , which does not satisfy either of the two bitonic permutations with $ n=3 $ , therefore the answer is 0. In the second test case, the expected permutation must be of the form $ [?,3,2] $ , which only satisfies the bitonic permutation $ [1,3,2] $ , therefore, the answer is 1.