Excellent Arrays

2000ms

262144K

Description:

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:

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:

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

Sample Input:

Sample Output:

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:

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

Informação

Provedor Codeforces

Código CF1550D