Нэгэн $A$ намын уулзалтан дээр сайд Пэйвэл хотын ус зайлуулах сувгийн системийг сайжруулан шинэ хоолой барихыг санаачилжээ.

Хот нь $n × m$ тэгш өнцөгт хэлбэртэй талбайтай. Энэ талбай нь нэгж квадратуудад хуваагдсан. Квадрат болгон нь хоосон (хоолой энэ дээр баригдах боломжтой) эсвэл дүүрэн (хоолой энэ дээр баригдах боломжгүй) байна. Хоосон квадрат болгон '$.$' тэмдэгтээр тэмдэглэгдэнэ. Аарин дүүрэн квадрат болгон нь '$#$' тэмдэгтээр тэмдэглэгдэнэ.

Хоолой нь дараах шаардлагуудыг хангах ёстой:

• Хоолой нь $1$ өргөнтэй олон шулуунуудын нийлбэр байх ёстой,
• Хоолой хоосон квадрат дээр л баригдах ёстой,
• Хоолой нь талбайн ирмэгээс эхлэх ёстой, гэхдээ булангаас эхэлж болохгүй,
• Хоолой нь талбайн ирмэг дээр дуусах ёстой, гэхдээ буланд дуусч болохгүй,
• Хоолой нь хамгийн ихдээ 2 удаа л эргэх боломжтой ($90$ градусаар),
• Хоолой нь хүрээний квадратуудад зөвхөн 2-хон удаа орох боломжтой (хүрээний гэдэг нь хамгийн захын квадратуудыг хэлж байгаа болно),
• Хэрвээ хоолой нь ганцхан шулуунаас бүтэж байвал түүний эцсийн байрлалын ирмэг нь эхлэлийн байрлалын ирмэгээс ялгаатай байх ёстой,
• Хоолойны хүрээний бус квадрат болгонд яг 2 ширхэг хоолой агуулж буй хөрш квадрат байх ёстой,
• Хоолойны хүрээний квадрат болгонд яг 1 ширхэг хоолой агуулж буй хөрш квадрат байх ёстой.

Энд хэдэн зөвшөөрөгдсөн хоолойны зураглал байна:

           ....#            ....#            .*..#  
           *****            ****.            .***.  
           ..#..            ..#*.            ..#*.  
           #...#            #..*#            #..*#  
           .....            ...*.            ...*.

Энд хэдэн зөвшөөрөгдөөгүй хоолойны зураглал байна:

           .**.#            *...#            .*.*#  
           .....            ****.            .*.*.  
           ..#..            ..#*.            .*#*.  
           #...#            #..*#            #*.*#  
           .....            ...*.            .***.

Эдгээр жишээнд хоолойг '$ * $' тэмдэгтээр илэрхийлэв.

Танаас хотод яг нэг хоолой байрлахаар хэдэн төрлийн ялгаатай арга байгааг тооцоолдог програм бичихийг гуйжээ.

Хэрвээ 2 арга замын хоолойнуудын дор хаяж 1 квадрат нь ялгаатай байвал эдгээр 2 арга замыг хоорондоо ялгаатай гэж үзнэ.

Оролт

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

Дараагийн $n$ ширхэг мөрний мөр болгон $m$ ширхэг тэмдэгт агуулна. Энэ нь хотын зураглал юм.

Хэрвээ зураглалын квадрат '$.$' тэмдэглэгдсэн байвал квадрат нь хоосон бөгөөд хоолойг бариж болно гэсэн үг.

Хэрвээ зураглалын квадрат '$#$' тэмдэглэгдсэн байвал квадрат нь дүүрэн бөгөөд хоолойг бариж болохгүй гэсэн үг.

Гаралт

Эхний мөрөнд хоолойг барих ялгаатай арга замын тоог нэг бүхэл тоогоор илэрхийлэн хэвлэнэ үү.

Эхний жишээнд хоолойг барих 3-н арга зам байна (Хоолойн квадратууд нь '$ * $' тэмдэгтээр тэмдэглэгдсэн):

       .*.        .*.        ...  
       .*#        **#        **#  
       .*.        ...        .*.