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.


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


-----Examples-----

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

Source: codeforces | Difficulty: HARD
Tags: Combinatorics

Implementation

Number theory

Dynamic programming

Mathematics


Solutions:
mod = 1000000007

def check(pos, val):
	if pos == kk and val != ss:
		return False
	if pos == tt and val != pp:
		return False
	return True

def solve():
	global n, kk, tt, ss, pp
	(n, kk, tt, ss, pp) = map(int, input().split())
	global dp
	dp = [[0 for i in range(n + 2)] for j in range(n + 2)]
	for i in range(2, n, 1):
		if check(i, n):
			dp[i][i] = 1
	for i in range(n, 0, -1):
		for j in range(i, n + 1):
			val = n - (j - i + 1)
			if check(i - 1, val):
				dp[i - 1][j] = (dp[i - 1][j] + dp[i][j]) % mod
			if check(j + 1, val):
				dp[i][j + 1] = (dp[i][j + 1] + dp[i][j]) % mod
	print(int(dp[1][n]))
__t = int(input())
while __t > 0:
	__t -= 1
	solve()