Шашлык evi#7502
Gənc Vaxanq Bumeranq dünyaca məşhur şaurma fast-foodunda şaurma hazırlayır. Hər bir şaurma bir çox inqrediyentdən ibarətdir.
Bu səhər Vaxanqdan şaurma hazırlamaq sifarişi alınıb. Əvvəlcə birinci şaurmaya q_1 inqrediyent qoyur, sonra ikinci şaurmaya q_2 inqrediyent və s. Vaxanq üçün bir inqrediyenti şaurmaya qoymaq bir saniyə çəkir, buna görə də -ci şaurmanı hazırlamaq üçün q_i saniyə kifayətdir. Bir şaurmanı bitirdikdən sonra dərhal digərini hazırlamağa başlayır.
Vaxanq tez-tez sevimli bumeranqı haqqında xəyal edir, şaurma hazırlayarkən. Hər xəyal anı dəqiq bir saniyə davam edir və məhz bu saniyədə Vaxanq bir inqrediyenti şaurmaya qoymağı unudur. Xoşbəxtlikdən, o, heç vaxt t + 1 saniyəlik hər hansı bir müddət ərzində iki dəfə xəyal etmir.
Bumeranq haqqında xəyal etdiyi üçün bəzi şaurmalar tələb olunan qədər inqrediyentə malik olmur, lakin müştərilər xoşbəxt qalırlar, əgər -ci şaurma ən azı x_i inqrediyentə malikdirsə.
Vaxanq iş zamanı xəyal edə biləcəyi yolların sayını hesablamaq istəyir, bütün müştəriləri məmnun saxlamaq şərti ilə. Ona kömək edə bilərsinizmi? Real cavab çox böyük ola bilər, buna görə də onu 10^9 + 7 modulu ilə hesablamaq lazımdır.
Birinci sətir iki tam ədəd və t~(1 \le n \le 1000, 0 \le t \le 100) — şaurmaların sayı və xəyal etmələr arasında mümkün olan ən az vaxt (saniyə ilə).
Növbəti sətirin hər biri iki tam ədəd q_i, x_i~(1 \le q_i \le 250, 0 \le x_i \le q_i) — -ci şaurmadakı inqrediyentlərin sayı və -ci müştərini xoşbəxt etmək üçün lazım olan minimum inqrediyent sayı.
Bir ədəd çıxarın — xəyal etmə saniyələrini bölüşdürmə yollarının sayı, 10^9 + 7 modulu ilə.
Nümunə 1