Козы между скалой и снегом
Горная коза пасётся на узком склоне между рекой и снегом. Высоту склона разбили на уровни от 0 (у самой реки) до h (у кромки снега). Каждую минуту коза поднимается на один уровень вверх или спускается на один уровень вниз, но никогда не заходит в реку (ниже уровня 0) и на снег (выше уровня h).
Утром коза была на уровне a, а через N минут пастух увидел её на уровне b. Сколько существует различных маршрутов козы? Маршрут — это последовательность уровней через каждую минуту.
Ответьте на T вопросов, ответы выведите по модулю 10⁹ + 7.
Входные данные
В первой строке — число T (1 ≤ T ≤ 10⁵). В каждой из следующих T строк — четыре целых числа N h a b (1 ≤ N ≤ 10⁶, 1 ≤ h ≤ 10⁶, 0 ≤ a, b ≤ h). Сумма всех N не превосходит 10⁷.
Выходные данные
Для каждого вопроса выведите количество маршрутов по модулю 10⁹ + 7.
Пример 1
Вход:
3
4 2 0 0
4 1 0 0
6 100 3 5
Выход:
2
1
15
Пояснение
На рисунке — маршруты из первого вопроса: за 4 минуты из уровня 0 в уровень 0 при h = 2 можно пройти двумя путями (0 1 0 1 0 и 0 1 2 1 0).
Система оценивания
Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 20 % тестов N, h ≤ 200.
Подсказка
Принцип отражения: пути, касающиеся запретного уровня, можно взаимно однозначно отразить.
Комментарии