D. Отличные массивы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Назовем целочисленный массив $$$a_1, a_2, \dots, a_n$$$ хорошим, если $$$a_i \neq i$$$ для всех $$$i$$$.

Пусть $$$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$$$.

Пример
Входные данные
4
3 0 3
4 -3 5
42 -33 55
69 -42 146
Выходные данные
4
10
143922563
698570404
Примечание

В первом наборе входных данных, можно показать, что максимальное $$$F(a)$$$ среди всех хороших массивов $$$a$$$ равно $$$2$$$. Отличными являются следующие массивы:

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