eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Шашлычная

Шашлычная

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Молодой человек Вахтанг Бумеранг делает шашлыки на всемирно известной шашлычной фаст-фуда. Каждый шашлык содержит множество ингредиентов.

Этим утром Вахтанг получил заказ сделать n шашлыков. Сначала в первый шашлык он кладет q_1 ингредиент, затем он кладет во второй шашлык q_2 ингредиентов и так далее. Вахтангу достаточно одной секунды чтобы положить один ингредиент в шашлык, поэтому достаточно q_i секунд чтобы сделать i-ый шашлык. Когда он завершает один шашлык, то сразу же приступает к приготовлению другого.

Вахтанг часто мечтает о своем любимом бумеранге, делая шашлыки. Каждый момент мечтания длится ровно одну секунду, и именно в эту секунду Вахтанг забывает положить один ингредиент в шашлык. К счастью, он никогда не мечтает дважды в любой промежуток времени из t + 1 секунд.

Из-за мечты о бумеранге некоторые шашлыки содержат меньше ингредиентов чем требуется, однако посетители остаются счастливыми если i-ый шашлык содержит в себе как минимум x_i ингредиентов.

Вахтанг хочет подсчитать количество способов, которыми сможет помечтать во время работы, сохраняя всех клиентов довольными. Вы можете помочь ему? Реальный ответ может быть очень большим, поэтому Вы должны вычислить его по модулю 10^9 + 7.

Входные данные

Первая строка содержит два целых числа n и t~(1 \le n \le 1000, 0 \le t \le 100) — количество шашлыков и наименьшее возможное время между мечтаниями в секундах.

Каждая из следующих n строк содержит два целых числа q_i, x_i~(1 \le q_i \le 250, 0 \le x_i \le q_i) — количество ингредиентов в i-ом шашлыке и наименьшее число ингредиентов для того чтобы i-го посетителя сделать счастливым.

Выходные данные

Выведите одно число — количество вариантов распределить секунды мечтаний, взятое по модулю 10^9 + 7.

Пример

Входные данные #1
3 1
4 3
2 2
2 1
Выходные данные #1
15
Источник 2014 ACM NEERC, Northern Subregion, November 8, Problem K