合法双调排列

• 时间限制：1 秒
• 内存限制：256 MiB

题目描述

给定五个整数 $n$、$i$、$j$、$x$ 和 $y$。请你计算满足 $B_i = x$ 且 $B_j = y$ 的 $1$ 到 $n$ 的“bitonic”排列 $B$ 的个数。由于答案可能很大，请输出对 $10^9+7$ 取模后的结果。

“bitonic”排列是指这样一种排列：排列中的元素从开头开始严格递增，一直持续到某个下标 $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$。

输出格式

对于每组测试用例，输出一行，表示满足条件的 bitonic 排列的个数，对 $10^9+7$ 取模。

样例输入 1

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

样例输出 1

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$）单调递增，然后单调递减，则称其为 bitonic 数组。例如，$[2,5,8,6,1]$ 是一个 bitonic 数组，$k=3$，但 $[2,5,8,1,6]$ 不是（先递增到 $k=3$，然后递减，再递增）。

bitonic 排列是指满足上述 bitonic 性质的排列。例如，$[2,3,5,4,1]$ 是一个 bitonic 排列，但 $[2,3,5,1,4]$ 不是（不满足 bitonic 性质），$[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]$。其中，bitonic 排列为 $[1,3,2]$ 和 $[2,3,1]$。

在第一个测试用例中，期望的排列形式为 $[2,?,3]$，这不满足 $n=3$ 的两个 bitonic 排列，因此答案为 $0$。

在第二个测试用例中，期望的排列形式为 $[?,3,2]$，只满足 bitonic 排列 $[1,3,2]$，因此答案为 $1$。

数据范围