CF1763D.Valid Bitonic Permutations

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.

给你五个整数 $n$、$i$、$j$、$x$ 和 $y$。求满足 $B_i = x$ 且 $B_j = y$ 的 $1$ 到 $n$ 的双调排列 $B$ 的个数。由于答案可能很大，请对 $10^9+7$ 取模。

一个双调排列是指一个数字的排列，其元素先严格递增至某个下标 $k$（其中 $2 \le k \le n-1$），再严格递减至末尾。更多说明请参见注释部分。

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 \lt j$ and $x \ne y$.

每个测试包含多个测试用例。第一行包含一个整数 $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 \lt j$ 且 $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$.

对于每个测试用例，输出一行，包含满足上述条件的双调排列的数量对 $10^9+7$ 取模的结果。

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.

排列是指由 $1$ 到 $n$ 的 $n$ 个互不相同的整数以任意顺序组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（数组中数字 $2$ 出现了两次），$[1,3,4]$ 也不是排列（此时 $n=3$，但数组中出现了 $4$）。

当 $n \ge 3$ 时，一个包含 $n$ 个元素的数组被称为双调数组（bitonic array），如果其元素先严格递增至某个下标 $k$（其中 $2 \le k \le n-1$），再从该位置起严格递减至数组末尾。例如，$[2,5,8,6,1]$ 是一个双调数组，对应 $k=3$；但 $[2,5,8,1,6]$ 不是双调数组（元素先递增至 $k=3$，然后递减，之后又再次递增）。

双调排列（bitonic permutation） 是指同时满足排列定义与上述双调性质的数组。例如，$[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。