Шашлычная

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

Этим утром Вахтанг получил заказ сделать $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$.

Примеры