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