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

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

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.