Шашлична#7502
Молодий чоловік Вахтанг Бумеранг готує шашлики у всесвітньо відомій шашличній фаст-фуді. Кожен шашлик містить безліч інгредієнтів.
Цього ранку Вахтанг отримав замовлення приготувати шашликів. Спочатку в перший шашлик він кладе q_1 інгредієнт, потім у другий шашлик — q_2 інгредієнтів, і так далі. Вахтангу потрібна лише одна секунда, щоб покласти один інгредієнт у шашлик, тому для приготування -го шашлика йому потрібно q_i секунд. Як тільки він завершує один шашлик, одразу ж починає готувати наступний.
Вахтанг часто мріє про свій улюблений бумеранг під час приготування шашликів. Кожна мрія триває рівно одну секунду, і саме в цю секунду Вахтанг забуває покласти один інгредієнт у шашлик. На щастя, він ніколи не мріє двічі в будь-який проміжок часу з t + 1 секунд.
Через мрії про бумеранг деякі шашлики можуть містити менше інгредієнтів, ніж потрібно, але відвідувачі залишаються задоволеними, якщо -ий шашлик містить принаймні x_i інгредієнтів.
Вахтанг хоче підрахувати кількість способів, якими він може мріяти під час роботи, зберігаючи всіх клієнтів задоволеними. Ви можете допомогти йому? Реальна відповідь може бути дуже великою, тому ви повинні обчислити її за модулем 10^9 + 7.
Перший рядок містить два цілих числа і t~(1 \le n \le 1000, 0 \le t \le 100) — кількість шашликів і найменший можливий час між мріями в секундах.
Кожен з наступних рядків містить два цілих числа q_i, x_i~(1 \le q_i \le 250, 0 \le x_i \le q_i) — кількість інгредієнтів у -му шашлику і мінімальна кількість інгредієнтів, щоб -ий відвідувач був задоволений.
Виведіть одне число — кількість варіантів розподілити секунди мрій, взяте за модулем 10^9 + 7.
Приклад 1