Masala #MZSG4YFRAF

Xotira 128 MB Vaqt 1000 ms
14

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.


Kiruvchi ma'lumotlar:

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.


Chiquvchi ma'lumotlar:

Maydonni tanlab olish mumkin bo’lgan barcha usullar sonini chiqaring.


Misollar
# input.txt output.txt
1
9 10
******.***
**.**.**.*
*.**.*..*.
****.*****
.***..*.*.
*********.
*****..**.
**********
***...*.**
35
2
3 5
*.***
*...*
**..*
14