D. Домино хивс

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

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

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

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

...Майк ТВ танитай дахин мэндэлж байна.

Нэг хэвийн тавилгаасаа уйдаж байна уу? Сонирхолтой өөрчлөлтийг даруухан орон сууцандаа хийхийг мөрөөдөж сууна уу? Тэгвэл бидэнд танд санал болгох зүйл байна.

Энэхүү Домино хивс $99.99 үнэтэй бөгөөд таны амьдралыг өөрчлөх болно. Та шалан дээрээ, хана дээрээ, бүр таазан дээрээ байршуулах боломжтой. Үүнээс бусад ...

Сурталчилгааг үзчихээд, вирус Хексадецимал Домино хивсийг худалдаж аваад өмнө нь зургаа даруулахыг хүсч байв. Мэдээж вирус хэзээч онцгой эрхтэй хивс авч мөнгөө үрэхгүй. Тэгээд тэр машин дүүрэн Домино захиалж өөрөө угсрахаар шийдэв.

Жинхэнэ Домино хивс $n × m$ хэмжээтэй дөрвөлжин талбараас үүснэ. Дөрвөлжин болгонд хагас домино байх ба босоогоор эсвэл хөндлөнгөөр нь хөршүүдээс нь хамааралгүйгээр эргүүлж болно. Босоогоор эргүүлсэн домино дараах байдлаар харагдана.

Хөндлөнгөөр эргүүлсэн домино дараах байдлаар харагдана.

Зарим хагас домино нар ижилхэн харагдах боловч нөгөө хагас нь өөр байна гэдгийг мэдэгдэе.

Хексадецималын худалдаж авсан домино хуваагддаггүй $1 × 2$ хэмжээтэй чипүүд байдаг ба босоогоор эсвэл хэвтээгээр байна. Хэрэв чип босоогоороо бол хагас доминонууд босоогоороо, хэвтээгээрээ бол хагас доминонууд хэвтээгээрээ байна.

Доорх зурганд боломжит болон боломжгүй доминонуудыг үзүүлэв.

Вирус Хексадецимал өөрийнхөө Домино хивсийг дараах нөхцлийг хангадаг байхаар урлана :

  • хивсний дөрвөлжин бүрт домино байна, ө.х. хоосон дөрвөлжин байхгүй;
  • бүх доминонууд хивсэнд давхралдалгүйгээр багтаж байна;
  • хэрэв хэвтээ доминогийн зүүн хагас нь $j$ баганад орсон бол зүүн хагас нь $j - 1$ эсвэл $j + 1$ баганад байдаг хэвтээ домино байж болохгүй.

Өөрийнхөө Домино хивсийг угсрахын өмнө вирус дээрх нөхцлийг хангах хэдэн боломж байгааг $10^{9} + 7$-д хуваахад гарах үлдэгдэлийг мэдэхийг хүсчээ.

Та вирусд хязгааргүй олон домино байгаа гэж үзэж болно.

Оролт

Эхний мөрөнд $n$ ба $m$, зайгаар тусгаарлагдан өгөгдөнө - Домино хивсийн хэмжээ ($1 ≤ n, m ≤ 250$). Дараагийн $4n + 1$ мөр бүр $4m + 1$ тэмдэгт агуулна.

Доминогийн хагас бүр $3 × 3$ хэмжээтэй дөрвөлжнөөр илэрхийлнэ.'O'$ тэмдэгт нүхийг, '.'$ тэмдэгт битүү хэсгийг тус тус төлөөлнө.

$3 × 3$ дөрвөлжин болгон хөршүүдээ '#'$ тэмдэгтээр тусгаарлагдсан байна.

Дөрвөлжин болгонд дээр дурьснаар зөв хагас домино өгөгдөнө.

Өмнөх-тестүүдэд Домино хивс $2 × 2$ болон $4 × 4$ хэмжээтэй байна.

Гаралт

Хариу болох ганц тоо, Домино хивсийг $1 × 2$ хэмжээтэй стандарт доминогоор угсарч болох боломжийн тоог $10^{9} + 7$-д хуваахад гарах үлдэгдэл.

Орчуулсан: Б.Алтангэрэл

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

Оролт
3 4
#################
#O..#...#O.O#...#
#.O.#.O.#.O.#...#
#..O#...#O.O#...#
#################
#O.O#OOO#O.O#...#
#.O.#...#...#.O.#
#O.O#OOO#O.O#...#
#################
#O.O#...#O.O#...#
#...#...#...#.O.#
#O.O#...#O.O#...#
#################
Гаралт
3
Оролт
2 2
#########
#O.O#O.O#
#.O.#...#
#O.O#O.O#
#########
#...#O.O#
#...#...#
#...#O.O#
#########
Гаралт
2
Оролт
2 2
#########
#..O#O..#
#...#...#
#O..#..O#
#########
#O..#..O#
#...#...#
#..O#O..#
#########
Гаралт
0

Тэмдэглэл

Эхний жишээндэх боломжит угсралтыг дараах зургуудад үзүүлэв.

Буруу угсралт нь :

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