Masala #MZSG4YFRAF
Viariantlar soni
Yo’ldosh yaqinda uy qurish uchun shahardan yer maydoni sotib oldi. Uning yer maydoni \(nxm\) lik to’g’ri to’rtburchak shaklida bo’lib, ba’zi yerlarida daraxtlar bor. Yo’ldosh tabiatni juda yaxshi ko’rganligi uchun daraxtlarni kesib tashlashni xohlamadi. Shuning uchun u maydon ichidan tomonlari berilgan maydon tanomlariga parallel va bitta ham daraxt bo’lmagan to’g’ri to’rtburchak shaklidagi maydonga uy qurish uchun tanlab olmoqchi. Yo’ldosh uning necha xil variant bor ekanligini bilishga qiziqib qoldi. Unga bu masalada yordam bering.
Birinchi qatorda maydon o’lchamlari \(n\) va \(m\) sonlari berilgan\((1≤n,m≤10^3).\)
Keyingi \(n\) ta qatorda har birida \(m\) tadan simvollar berilgan. Ularning qiymati\(‘*’\)bo’lsa bu katakda daraxt bor, \(‘.’\) bo’lsa daraxt yo’q ekanligini bildiradi.
Maydonni tanlab olish mumkin bo’lgan barcha usullar sonini chiqaring.
# | input.txt | output.txt |
---|---|---|
1 |
9 10 ******.*** **.**.**.* *.**.*..*. ****.***** .***..*.*. *********. *****..**. ********** ***...*.** |
35 |
2 |
3 5 *.*** *...* **..* |
14 |