J. Non-Intersecting Arcs
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Payas is bored and is lost drawing figures in his notebook. To have fun he writes the numbers from $$$1$$$ to $$$n$$$ in that order, takes a permutation $$$p$$$ of length $$$n$$$ and goes on drawing arcs from $$$p_i$$$ to $$$p_{i+1}$$$. Interestingly he finds that no $$$2$$$ arcs intersect except maybe at the endpoints! Being curious he sets out to find the number of permutations starting and ending with the same elements as $$$p$$$ for which this holds...

Formally you need to find the number of permutations $$$p$$$ of length $$$n$$$ for which the following condition is satisfied:

  • For any $$$2$$$ distinct indices $$$i,j \lt n$$$ it doesn't hold that $$$\min(p_i,p_{i+1}) \lt \min(p_j,p_{j+1}) \lt \max(p_i,p_{i+1}) \lt \max(p_j,p_{j+1})$$$.
  • $$$p_1 = x.$$$
  • $$$p_n = y.$$$
Since the count can be large, output it modulo $$$10^9+7$$$.
Input

The first line of the input is a single integer $$$t$$$ ($$$1 \leq t \leq 2 \times 10^5$$$), the number of test cases.

Each of the next $$$t$$$ lines consist of $$$3$$$ space separated integers $$$n$$$ ($$$2 \leq n \leq 10^6$$$), the length of the permutation, $$$x$$$, the first element of the permutation and $$$y-$$$ the last element of the permutation ($$$1 \leq x, y \leq n, x \neq y$$$).

It is guaranteed that the sum of $$$n$$$ over all test-cases does not exceed $$$10^6$$$.

Output

For each test case, print a single integer denoting the number of permutations satisfying the problem condition modulo $$$10^9+7$$$.

Example
Input
3
3 1 2
4 3 4
5 1 4
Output
1
1
3
Note

In the first test case, the desired permutations are $$$[1,3,2]$$$.

In the second test case, the desired permutations are $$$[3,2,1,4]$$$.

In the third test case, the desired permutations are $$$[1,5,2,3,4]$$$, $$$[1,2,3,5,4]$$$ and $$$[1,2,5,3,4]$$$.

The permutation $$$[1,3,2,5,4]$$$ does not satisfy the problem constraints, because the arc that goes from $$$1 \rightarrow 3$$$ intersects the arc going from $$$2 \rightarrow 5$$$. Or in formal notation, for $$$i=1$$$ and $$$j=3$$$, $$$\min(p_1,p_2) \lt \min(p_3,p_4) \lt \max(p_1,p_2) \lt \max(p_3,p_4)$$$, thus violating the problem condition.