D. Excellent Arrays
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\).
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\).
For each test case, print the number of excellent arrays modulo \(10^9 + 7\).
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]\).