D. Дима ба дүрс

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

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

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

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

Дима дөрвөлжин цаасны хэсэг дээр зураг зурах дуртай. Гэхдээ үүнээс илүүгээр Дима өөрийнх нь дуртай дүрсийг буулган үлдээсэн зурагт үнэхээр дуртай.

$n × m$ хэмжээ бүхий дөрвөлжин цаасны хэсэг нь $n$ мөр болон $m$ баганаас тогтох хүснэгтээр дүрслэгдэх юм. Хоосон дөрвөлжин цаасан дээрх бүх нүднүүд нь цагаан байна. Дима хоосон цаасан дээрх хэсэг хараар будсан нүднүүдийн үүсгэх дүрсийг зураг хэмээн тодорхойлох юм. Хэрэв зураг нь дараах нөхцөлүүдийг хангаж байвал уг зургийг Дима-ын дуртай дүрсүүдийн нэгийг буулгасан байна гэж үзнэ.

  • Зураг нь дор хаяж нэг будагдсан нүд агуулсан байна;
  • Бүх будагдсан нүднүүд нь холбоост олонлог үүсгэнэ, өөрөөр хэлбэл та аль ч будагдсан нүднээс аль бусад нүдэнд хүрч чадна (ингэхдээ та нэг нүднээс зэргэлдээ нүд уруу нүүх замаар хүрэх юм);
  • $(x_{1}, y_{1})$ гэсэн координаттай будагдсан нүднээс $(x_{2}, y_{2})$ гэсэн координаттай будагдсан нүд хүртэл зөвхөн будагдсан нүднүүдээр дамжин хүрэхэд шаардлагатай нүүдлийн хамгийн бага тоо нь $|x_{1} - x_{2}| + |y_{1} - y_{2}|$-той тэнцүү байна.

Одоо Дима $n × m$ хэмжээтэй цаасны хэсэг дээр түүний дуртай дүрсүүдийн нэгийг буулгасан байх хэчнээн зураг байгааг олохыг хүсжээ. Уг тоог $1000000007 (10^{9} + 7)$ модулаар бодож олно уу.

Оролт

Эхний мөрөнд цаасны хэсгийн хэмжээ болох 2 бүхэл тоо $n$ болон $m$ өгөгдөнө $(1 ≤ n, m ≤ 150)$.

Гаралт

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

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

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

Оролт
2 2
Гаралт
13
Оролт
3 4
Гаралт
571
Сэтгэгдлүүдийг ачааллаж байна...