D. Хичээлийн хуваарь

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

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

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

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

Петя компьютерийн тоглоом тоглоод үлдсэн цагаараа их сургуулийн хичээлд суудаг байв.

Их сургуульд өдөр бүр хоёр цаг хичээл ордог. Хичээл бүр урт гудмын дагуу байрласан $M$ тооны өрөөний аль нэгд орно.

Оюутнууд нийт $N$ бүлэгт хуваагдсан бөгөөд хичээлийн хуваарьд дараах зүй тогтол ажиглагдав: эхний хичээлд сууж буй бүлгийн тоо, $2$-р цагийн хичээлд орж байгаа бүлгийн тооноос хэтрэхгүй байлаа.

Петя бүх бүлэгт зориулсан хичээлийн хуваарь зохиох нийт боломжуудын тоог олохоор шийдэв. Хичээлийн хуваарь нь $2N$ тооноос бүтэх бөгөөд: бүлэг бүрийн хувьд эхний цагийн хичээл орох өрөөний дугаар ба дараагийн цагийн хичээл орох өрөөний дугаар байна.

Харамсалтай нь тэр тооцоолж байснаа будилсан бөгөөд зөвхөн дараах нөхцлүүдийг хангах хичээлийн хуваариудыг тоолохоор болов:

  1. $i$-р өрөөний эхний хичээлд яг $X_i$ тооны бүлэг суух ёстой.
  2. $i$-р өрөөнд $Y_i$-аас их тооны бүлэг байх ёсгүй.

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

Оролт

Эхний мөрөнд өрөөний тоо $M$ ($1 ≤ M ≤ 100$).

Хоёр дахь мөрөнд $M$ ширхэг бүхэл тоо зайгаар тусгаарлагдан өгөгдөнө: $X_{i}$ ($0 ≤ X_{i} ≤ 100$) $i$-р өрөөнд эхний хичээлд суух бүлгийн тоо.

Гурав дахь мөрөнд $M$ ширхэг бүхэл тоо зайгаар тусгаарлагдан өгөгдөнө: $Y_{i}$ ($0 ≤ Y_{i} ≤ 100$) $i$-р өрөөнд хамгийн ихдээ нэгэн зураг сууж багтах бүлгийн тоо.

$X_{i} ≤ Y_{i}$ нөхцөл үргэлж биелэнэ. $X_{i}$-үүдийн нийлбэр нь эерэг бөгөөд $1000$-аас хэтрэхгүй.

Гаралт

Хариу болох нэг тоог $10^{9} + 7$-д хуваасан үлдэгдлийг хэвлэнэ үү.

Орчуулсан: gmunkhbaatarmn

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

Оролт
3
1 1 1
1 2 3
Гаралт
36
Оролт
3
1 1 1
1 1 1
Гаралт
6

Тэмдэглэл

Хоёр дахь жишээнд эхний болон хоёр дахь цагийн хичээлүүд бүх бүлгийн хувьд нэг ангид болно. Тийм учраас ангиудын байр сэлгэлтээс хамаарч хичээлийн хуваариуд өөр өөр байна. Өөрөөр хэлбэл: $3! = 6$.

Сэтгэгдлүүдийг ачааллаж байна...