Valid Bitonic Permutations

Description:

Input:

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$$$.

Output:

For each test case, output a single line containing the number of bitonic permutations satisfying the above conditions modulo $$$10^9+7$$$.

Sample Input:

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

Sample Output:

0
1
1
1
3
0
4788

Note:

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.