如果每个 $$$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]$$$.