D. Шениа ба даалуу

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

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

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

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

Шениа эвлүүлдэг тоглоомуудад маш их дуртай. Тэр ялангуяа даалуутай эвлүүлдэг тоглоомуудад их дуртай. Ийм эвлүүлдэг тоглоомын жишээг доорх зурагт харуулсан байна.

Эвлүүлдэг тоглоом нь хориотой нүднүүдтэй (хар дөрвөлжингүүд), даалуу агуулсан $3 × n$ хүснэгт байна. Хэрвээ доорх нөхцөлүүд биелэж байвал эвлүүлдэг тоглоомыг зөв гэж үзнэ:

  • даалуу бүр хүснэгтийн яг хоёр хориотой биш нүдийг эзлэх;
  • ямар ч хоёр даалуу хүснэгтийн нэг нүдийг эзлэхгүй;
  • хүснэгтийн яг нэг ширхэг хориотой биш нүдийг ямар ч даалуу эзлээгүй байх (зураг дээр цэгээр дүрсэлсэн).

Эвлүүлдэг тоглоомыг эвлүүлэхийн тулд танд хоосон нүдийг эхлэх байрлалаас нь тодорхой байрлалд зөөх хэд хэдэн алхам хэрэгтэй. Нэг үйлдэл нь эвлүүлдэг тоглоомыг зөв хэвээр нь даалууг хоосон нүдрүү хөдөлгөх байна. Хэвтээ даалуунууд зөвхөн хэвтээ чиглэлд хөдөлж чадах бол босоо даалуунууд нь зөвхөн босоо чиглэлд хөдөлнө. Та даалуунуудыг эргүүлж чадахгүй. Зурагт боломжит үйлдлийг дүрсэлсэн байна.

Шениад хориотой нүднүүд болон цэгтэй нүдийг агуулсан $3 × n$ хүснэгт байна. Мөн Шениад маш олон ижилхэн даалуу байна. Одоо Шениа хэрвээ тэр хүснэгтэн дээр даалуунуудыг тавиад хичнээн ялгаатай зөв эвлүүлдэг тоглоом үүсгэх боломжтой вэ гэж гайхаж байна. Мөн Шениа гарч буй эвлүүлдэг тоглоомонд цэгтэй нүд нь хоосон нүд байх болно гэж хүсч байна. Эвлүүлдэг тоглоом нь хийж болох ядаж нэг үйлдэл агуулах ёстой.

Шениад тодорхойлсон эвлүүлдэг тоглоомуудыг тоолоход туслана уу. Энэ тоо нь маш их байж болох учир $1000000007$ $(10^{9} + 7)$ тоонд хуваагаад гарсан үлдэгдлийг хэвлэнэ үү.

Оролт

Эхний мөрөнд бүхэл тоо $n$ $(3 ≤ n ≤ 10^{4})$ байх буюу эвлүүлдэг тоглоомын хэмжээ юм. Дараагийн гурван мөр тус бүрт $n$ тэмдэгт байх буюу хүснэгтийн тайлбар байна. Хэрвээ харгалзах нүд нь хориотой нүд байвал $i$-р мөрийн $j$-р тэмдэгт нь "$X$" байна; хэрвээ харгалзах нүд нь хориотой биш байвал "$.$" байна; хэрвээ харгалзах нүд нь цэгтэй нүд байвал "$O$" байна.

Хүснэгтийн нэг л нүд нь цэгтэй нүд байна. Цэгтэй нүдтэй ядаж нэг цэгээр холбогдсон хүснэгтийн бүх нүднүүд хориотой биш нүд байна.

Гаралт

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

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

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

Оролт
5
....X
.O...
...X.
Гаралт
1
Оролт
5
.....
.O...
.....
Гаралт
2
Оролт
3
...
...
..O
Гаралт
4

Тэмдэглэл

Хоёр эвлүүлдэг тоглоомыг харьцуулаад хэрвээ нэг тоглоомон дээр нэг даалуу агуулсан хоёр нүд нөгөө тоглоомон дээр агуулаагүй бол ялгаатайд тооцно.

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