E. Модон Хашаа

хугацааны хязгаарлалт 3 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Вася саяхан хэсэг газар худалдан авсан бөгөөд уг газраа тойруулан модон хашаа барихаар болжээ.

Тэрээр "Модон Хавтан" гэж нэрлэгдэх хашаанд хэрэглэгдэх модон хавтан үйлдвэрлэдэг нэгэн компани дээр очжээ. Вася бүтээгдэхүүнүүдийн каталог-ыг уншиж танилцсан бөгөөд уг компани $n$ ширхэг ялгаатай төрлийн модон хавтан зардаг болохыг мэджээ. Компани $i$-р төрлийн модыг уг төрлийн модон хавтан үйлдвэрлэхэд ашигладаг бөгөөд модон хавтан нь $a_{i}$-г харьцах нь $b_{i}$ хэмжээ бүхий тэгш өнцөгт хэлбэртэй байх юм.

Вася уг компаниас модон хавтангуудаа захиалахаар болсон бөгөөд эдгээрийг ашиглан хашаагаа барихаар болжээ. Уг компанийн агуулах нь маш том болж таарсан ба иймд Вася төрөл болгоноос дурын тооны модон хавтан захиалж болох байв. Вася өөрөө хашаагаа барьж байгаа тул барих явцдаа модон хавтангуудаа эргүүлэн хэрэглэж болохыг анхаарна уу. Гэвч квадрат хэлбэртэй модон хавтанг эргүүлж болохгүй байна.

Вася $l$ урттай хашаа барих хэрэгтэй байгаа бөгөөд хашаагаа дурын байдлаар барихгүй юм. Тэрээр өөрийн барьсан хашаагаа үзэсгэлэнтэй харагдахыг хүсэж байв. Хэрэв хашаа нь зөвхөн дараах 2 нөхцөлийг 2-ууланг нь хангасан тохиолдолд бид уг хашааг үзэсгэлэнтэй гэж хэлнэ:

  • нэг төрлийн ямар ч 2 модон хавтан зэргэлдээ оршихгүй
  • хашааны эхний хавтан нь дурын урттай байх бөгөөд дараагийн хавтангаас эхлэн хавтан бүрийн урт нь өмнөх хавтангын өргөнтэй тэнцүү байна

Өөрөөр хэлбэл хэрэв хашааны $i$-р хавтан нь $i - 1$-р хавтангаас өөр төрлийн модон хавтан байх бөгөөд $i$-р хавтангын урт нь $i - 1$-р (2-оос эхлэх бүх $i$-ын хувьд) хавтангын өргөнтэй тэнцүү байвал уг хашааг үзэсгэлэнтэй гэж үзэх юм.

Одоо Вася өөрийн газартаа хашаа барих нийт хэчнээн хувилбар байгааг мэдэхийг хүсжээ. Таны даалгавар бол $l$ урттай ялгаатай үзэсгэлэнтэй хашаануудын тоог олох юм.

Хэрэв 2 хашааны хувьд харгалзах хашааны бүх модон хавтангууд нь төрөл болон эргүүлэлтээрээ ижилхэн байвал эдгээр 2 хашааг ижилхэн хашаа гэж үзнэ. Бусад тохиолдолд эдгээр хашаануудыг ялгаатай гэж үзэх юм. Бидний хайж буй тоо нь маш том тоо байж болох учраас та хариултыг $1000000007$ $(10^{9} + 7)$ модулаар бодон хэвлэнэ үү.

Оролт

Эхний мөрөнд 2 бүхэл тоо $n$ болон $l$ ($1 ≤ n ≤ 100, 1 ≤ l ≤ 3000$) өгөгдөх ба эдгээр нь харгалзан ялгаатай модон хавтангуудын төрлүүдийн тоо болон хашааны уртыг тус тус илэрхийлнэ. Дараагийн $n$ ширэг мөрөнд модон хавтангуудын төрлүүдийн тайлбар өгөгдөнө: $i$-дахь мөрөнд 2 бүхэл тоо $a_{i}$ болон $b_{i}$ ($1 ≤ a_{i}, b_{i} ≤ 100$) өгөгдөх ба эдгээр нь $i$-р төрлийн модон хавтангын хэмжээнүүдийг илэрхийлнэ. Мөрүүдэд өгөгдөх бүх тоонууд нь зайгаар тусгаарлагдсан байна.

Гаралт

Хайж буй тоог $1000000007$ ($10^{9} + 7$) модулаар бодсон утга болох ганц бүхэл тоог хэвлэнэ үү.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
2 3
1 2
2 3
Гаралт
2
Оролт
1 2
2 2
Гаралт
1
Оролт
6 6
2 1
3 2
2 5
3 3
5 1
2 1
Гаралт
20

Тэмдэглэл

Эхний жишээнд 3 урттай үзэсгэлэнтэй хашаа барих яг 2 хувилбар оршин байна:

  • 1 урттай, 2 өргөнтэй эхний төрлийн модон хавтанг хашааны эхний хавтан болгоно. 2 урттай, 3 өргөнтэй 2-дахь төрлийн модон хавтанг хашааны 2-дахь хавтан болгох ба ингэснээр хашааны урт нь 3 болох юм.
  • 2-дахь төрлийн нэг ширхэг модон хавтанг эргүүлэн хашааг барина. Ингэснээр таны хашаа 3 урттай, 2 өргөнтэй нэгэн хавтангаас тогтох юм.
Сэтгэгдлүүдийг ачааллаж байна...