Excellent Arrays
Contest: Educational Codeforces Round 111 (Rated for Div. 2)
Difficulty rating: 2300
Tags: binary search, combinatorics, constructive algorithms, implementation, math, sortings, two pointers

Let's call an integer array $$$a_1, a_2, \dots, a_n$$$ good if $$$a_i \neq i$$$ for each $$$i$$$.

Let $$$F(a)$$$ be the number of pairs $$$(i, j)$$$ ($$$1 \le i < j \le n$$$) such that $$$a_i + a_j = i + j$$$.

Let's say that an array $$$a_1, a_2, \dots, a_n$$$ is excellent if:

- $$$a$$$ is good;
- $$$l \le a_i \le r$$$ for each $$$i$$$;
- $$$F(a)$$$ is the maximum possible among all good arrays of size $$$n$$$.

Given $$$n$$$, $$$l$$$ and $$$r$$$, calculate the number of excellent arrays modulo $$$10^9 + 7$$$.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

The first and only line of each test case contains three integers $$$n$$$, $$$l$$$, and $$$r$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$-10^9 \le l \le 1$$$; $$$n \le r \le 10^9$$$).

It's guaranteed that the sum of $$$n$$$ doesn't exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, print the number of excellent arrays modulo $$$10^9 + 7$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, it can be proven that the maximum $$$F(a)$$$ among all good arrays $$$a$$$ is equal to $$$2$$$. The excellent arrays are:

1. $$$[2, 1, 2]$$$;
2. $$$[0, 3, 2]$$$;
3. $$$[2, 3, 2]$$$;
4. $$$[3, 0, 1]$$$.

Example input:
4
3 0 3
4 -3 5
42 -33 55
69 -42 146

Example output:
4
10
143922563
698570404

Editorial:
Firstly, let's learn the structure of good array $$$a$$$ with maximum $$$F(a)$$$. Suppose, $$$a_i = i + k_i$$$, then $$$a_i + a_j = i + j$$$ $$$\Leftrightarrow$$$ $$$k_i = -k_j$$$. In other words, we can group $$$a_i$$$ by $$$|k_i|$$$ and pairs will appear only inside each group. It's easy to prove that if the group has size $$$m$$$ then it's optimal to split it in half: one with $$$+k_i$$$ and other with $$$-k_i$$$. Then the number of pairs inside the group will be equal to $$$\left\lfloor \frac{m}{2} \right\rfloor \cdot \left\lceil \frac{m}{2} \right\rceil$$$.
It's also not hard to prove that in this case it's optimal to place all elements inside one group. In other words, it's optimal to make a half of all elements as $$$a_i = i + k$$$ and the other half as $$$a_i = i - k$$$ for some integer $$$k > 0$$$. Then $$$F(a) = \left\lfloor \frac{n}{2} \right\rfloor \cdot \left\lceil \frac{n}{2} \right\rceil$$$.
To achieve maximum $$$F(a)$$$ the excellent array should also have this structure. Let $$$\mathit{half} = \left\lfloor \frac{n}{2} \right\rfloor$$$. For a fixed $$$k$$$ if $$$n$$$ is even then we should choose exactly $$$\mathit{half}$$$ positions $$$i$$$ to set as $$$a_i = i + k$$$, but if $$$n$$$ is odd, we can choose either $$$\mathit{half}$$$ or $$$\mathit{half} + 1$$$ positions.
Let's analyze what happens with different $$$k$$$. Obviously, $$$k \ge 1$$$. While $$$k \le \min(1 - l, r - n)$$$ both $$$i + k$$$ and $$$i - k$$$ are in the segment $$$[l, r]$$$ for any $$$i$$$. In this case we can choose any $$$a_i$$$ as $$$i + k$$$, so there are exactly $$$\binom{n}{\mathit{half}}$$$ ways for even $$$n$$$ and $$$\binom{n}{\mathit{half}} + \binom{n}{\mathit{half} + 1}$$$ ways for odd $$$n$$$.
When $$$k > \min(1 - l, r - n)$$$ then for $$$i \in [1, \mathit{lf})$$$ (where $$$\mathit{lf} = \max(1, l + k)$$$) there is only one choice — to set $$$a_i = i + k$$$. Analogically, for $$$i \in (\mathit{rg}, n]$$$ (where $$$\mathit{rg} = \min(n, r - k)$$$) there is only choice to set $$$a_i = i - k$$$.
What remains is $$$\mathit{rg} - \mathit{lf} + 1$$$ elements without restrictions, so there are $$$\binom{\mathit{rg} - \mathit{lf} + 1}{\mathit{half} - (\mathit{lf} - 1)}$$$ ways to choose for even $$$n$$$ or $$$\binom{\mathit{rg} - \mathit{lf} + 1}{\mathit{half} - (\mathit{lf} - 1)} + \binom{\mathit{rg} - \mathit{lf} + 1}{\mathit{half} + 1 - (\mathit{lf} - 1)}$$$ ways for odd $$$n$$$.
Note that it's convenient to say that $$$\binom{n}{k} = 0$$$ if $$$k < 0$$$ or $$$n < k$$$, so we don't need extra checks.
Lastly, note that we can process all $$$k \in [1, \min(1 - l, r - n)]$$$ with one formula and there are only $$$O(n)$$$ of $$$k > \min(1 - l, r - n)$$$ with non-zero number of ways to choose, so we can iterate over all such $$$k$$$ straightforwardly.
The total complexity is $$$O(n \log{\mathit{MOD}})$$$ because of precomputation of factorials and inverse factorials to calculate $$$\binom{n}{k}$$$.