Козы между скалой и снегом


Отправить решение Решать в редакторе

Сложность: 80%
Очки: 100 (частичный балл)
Ограничение по времени: 2.0s
Ограничение по памяти: 256M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Горная коза пасётся на узком склоне между рекой и снегом. Высоту склона разбили на уровни от 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.

Подсказка

Принцип отражения: пути, касающиеся запретного уровня, можно взаимно однозначно отразить.


Комментарии

Еще нет ни одного комментария.