Шашлична

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

Цього ранку Вахтанг отримав замовлення приготувати $n$ шашликів. Спочатку в перший шашлик він кладе $q_1$ інгредієнт, потім у другий шашлик — $q_2$ інгредієнтів, і так далі. Вахтангу потрібно лише одна секунда, щоб покласти один інгредієнт у шашлик, тому для приготування $i$-го шашлика йому потрібно $q_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$.

Приклади