← 返回题目列表

Codeforces · 1550/D

D. 优秀的阵列

中文机器翻译题面 查看原题

如果每个 $$$i$$$ 都有 $$$a_i \neq i$$$,那么我们称整数数组为 $$$a_1, a_2, \dots, a_n$$$ 好。

令 $$$F(a)$$$ 为 $$$(i, j)$$$ ($$$1 \le i < j \le n$$$) 的数量,使得 $$$a_i + a_j = i + j$$$。

假设数组 $$$a_1, a_2, \dots, a_n$$$ 非常好,如果:

- $$$a$$$ 很好;
- $$$l \le a_i \le r$$$ 对于每个$$$i$$$;
- $$$F(a)$$$ 是所有大小为 $$$n$$$ 的好数组中可能的最大值。

给定$$$n$$$、$$$l$$$和$$$r$$$,计算优秀数组的数量模$$$10^9 + 7$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。

每个测试用例的第一行也是唯一一行包含三个整数 $$$n$$$、$$$l$$$ 和 $$$r$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$-10^9 \le l \le 1$$$; $$$n \le r \le 10^9$$$)。

保证 $$$n$$$ 的总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印优秀数组的数量模 $$$10^9 + 7$$$。

示例

输入 #1

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

输出 #1

4
10
143922563
698570404

注意

在第一个测试用例中,可以证明所有好数组$$$a$$$中的最大值$$$F(a)$$$等于$$$2$$$。优秀的数组有:

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