Жонн хүү гагнуурчин болохыг эрмэлздэг! Өнөөдөр тэр $n$ мөр, $m$ баганаас бүрдсэн $n × m$ хэмжээтэй хүснэгт зурав.

Хүснэгтийн нүд болгонд тэр хоолой зурна. Тэр зөвхөн $1$-с $4$ хүртэл дугаарлагдсан 4 төрлийн хоолой зурж чадна, доор харуулснаар:

Хоолой бүр 2 төгсгөлтэй, дээрх зурагд сумаар харуулсан болно. Жишээ нь: $1$-р хоолой дээрээ болон зүүн талдаа төгсдөг.

Жонн хэрвээ дор хаяж нэг хоолойн төгсгөл хүснэгтэн дотор өөр хоолойн төгсгөлтэй холбогдохгүй байвал хоолойн систем задарсан байна гэж үздэг. Доорх зурган дээр $1 × 2$ хэмжээтэй задарсан ба задраагүй хоолойн системийн жишээг харуулсан байна.

Одоо чамд Жонны зарим нүдийг нь дүүргэсэн хүснэгт өгөгдөнө. Нүд болгонд 4 төрлийн хоолойн аль нэг эсвэл хоосон гэж өгөгдөнө. Жонн хоолойн системийг задраагүй байхаар хэдэн ялгаатай аргаар бүх хоосон нүдийг дүүргэж чадах вэ? Гарах тоог $1000003$ ($10^{6} + 3$) модулиар ол.

Дор хаяж ганц л нүдний хоолой эргэсэн буюу өөр байвал энэ 2 угсралтыг өөр гэж тооцно.

Оролт

Эхний мөрөнд зайгаар тусгаарлагдсан 2 бүхэл тоо $n$ ба $m$ ($1 ≤ n, m, nm ≤ 510^{5}$) -- харгалзан мөр ба баганын тоог илэрхийлнэ. Дараагийн $n$ мөр бүрд яг $m$ тэмдэгт өгөгдөнө -- хүснэгтийг илэрхийлнэ. Тэмдэгт бүр нүдийг илэрхийлэх ба эдгээрийн аль нэг нь байна:

• "1$" - "4$" -- дээр дурдсан 4 төрлийн хоолой

• ".$" -- хоосон нүд

Гаралт

Хоолойн систем задраагүй байхаар гүйцэд угсрах боломжийн тоог $1000003$ ($10^{6} + 3$) модулиар хэвлэ. Хэрвээ задраагүй байхаар угсрах боломжгүй бол $0$ гэж хэвлэ.

Эхний жишээн дээр, хүснэгт анх дараах байдалтай байна.

Хоолойн систем задраагүй байхаар гүйцэд угсрах дараах 2 боломж л байна.

Хоёрдугаар жишээн дээр, өгсөн угсралт нь аль хэдийн задарсан байна. Иймд хоолойн систем задраагүй байх боломжгүй.

Сүүлийн жишээн дээр, доор үзүүлснээр угсрах цор ганц боломжтой.