Excellent Arrays

我们定义一个长度为 $n$ 的整数序列 $a$ 是好的仅当对于任意整数 $i\in[1,n]$，都有 $a_i\not=i$。 设 $F(a)$ 等于满足 $1\leq i<j\leq n,a_i+a_j=i+j$ 的 $(i,j)$ 对数。 我们定义一个长度为 $n$ 的序列 $a$ 是极好的，仅当： - $a$ 是好的。 - 对于任意整数 $i\in[1,n]$，$l\leq a_i\leq r$。 - $F(a)$ 的值是所有好的、长度为 $n$ 的序列中最大的。 给定 $n,l,r$，求极好的序列个数对 $10^9+7$ 取模后的结果。$T$ 组数据。 $1\leq T\leq10^3;$ $2\leq n,\sum n\leq2\times10^5;-10^9\leq l\leq1,n\leq r\leq10^9;$

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

4
3 0 3
4 -3 5
42 -33 55
69 -42 146

4
10
143922563
698570404

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