D. Грег ба Агуй

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

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

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

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

Грегт нэг хавтан бий. Хавтангийн дэлгэц нь $n × m$ хэмжээтэй тэгш өнцөгт, нүд бүр хар эсвэл цагаан байж чадна. Бид хавтангийн мөрийг дээрээс нь доош $1$-с $n$ хүртэл бүхэл тоогоор дугаарлаж авч үзнэ. Үүнтэй адилаар баганыг нь зүүнээс баруун тийш $1$-с $m$ хүртэл бүхэл тоогоор дугаарлана.

Грег дараах нөхцөлд хавтангийн дэлгэц агуй дүрсэлдэг гэж боддог:

  • Энд $l, l + 1, ..., r$ мөр бүрийн яг хоёр нүд нь хар байх $[l, r]$ $(1 ≤ l ≤ r ≤ n)$ хэсэг байгаа ба үлдсэн бүх мөрүүд зөвхөн цагаан нүднүүдтэй.
  • $i$ болон $j$ $(l ≤ i ≤ j ≤ t)$ дугаартай бүх хос мөрийн хувьд $i$ мөрийн хар нүднүүдийн баганын бүлэг (хар нүднүүдтэй баганууд) нь $j$ мөрийн хар нүднүүдийн баганын бүлгийн (хар нүднүүдтэй баганууд) дэд бүлэг байх $t$ $(l ≤ t ≤ r)$ мөрийн дугаар байх. Үүнтэй адилаар $i$ болон $j$ $(t ≤ i ≤ j ≤ r)$ дугаартай бүх хос мөрийн хувьд $j$ мөрийн хар нүднүүдийн баганын бүлэг (хар нүднүүдтэй баганууд) нь $i$ мөрийн хар нүднүүдийн баганын бүлгийн (хар нүднүүдтэй баганууд) дэд бүлэг байх.

Грег хавтан дээрээ агуй зурах хэдэн зам байгаа вэ гэж гайхаж байна. Хоёр зурган дээр өөр өөр өнгөтэй нүд байгаа бол уг хоёр зам нь ялгаатай гэж тооцогдоно.

Грегт туслана уу.

Оролт

Эхний мөрөнд хоёр бүхэл тоон утга $n$, $m$ байх ба хавтангийн дэлгэцийн хэмжээ $(1 ≤ n, m ≤ 2000)$.

Гаралт

Бодлогын хариултыг $1000000007$ $(10^{9} + 7)$ тоонд хуваагаад гарах үлдэгдлийг хэвлэ.

Орчуулсан: Г.Мэндбаяр

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

Оролт
1 1
Гаралт
0
Оролт
4 4
Гаралт
485
Оролт
3 5
Гаралт
451
Сэтгэгдлүүдийг ачааллаж байна...