Domino

Dora domino oynamağı çox sevir. O, n * m ölçülü bir cədvəl götürür, bəzi hüceyrələri dolu kimi işarələyir və sonra bütün boş hüceyrələri 2 * 1 ölçülü domino daşları ilə doldurmağa çalışır.

Doranın kiçik qardaşı Deni isə bacısına zarafat etməyi sevir. O, Dora olmadıqda, daha iki boş hüceyrəni dolu kimi işarələyir. Deni bunu elə etmək istəyir ki, bütün boş hüceyrələri domino daşları ilə doldurmaq mümkün olmasın.

Deniyə bu iki hüceyrəni neçə fərqli üsulla seçə biləcəyini hesablamağa kömək edin. Çünki Deni yalnız bir milyona qədər saya bilir, əgər bu üsulların sayı x-ə bərabərdirsə, onda min(x, 10^6) çıxarın.

Giriş məlumatları

Birinci sətir n və m tam ədədlərini (1 ≤ n, m ≤ 1000) ehtiva edir. Növbəti n sətir hər birində m simvol olan cədvəlin ilkin vəziyyətini ehtiva edir. "#" simvolu dolu hüceyrəyə, "." simvolu isə boş hüceyrəyə uyğundur. Ən azı iki boş hüceyrənin olduğu və bütün boş hüceyrələrin domino daşları ilə doldurula biləcəyi təmin edilir.

Çıxış məlumatları

Qoy x - Deninin iki hüceyrəni elə qeyd edə biləcəyi üsulların sayı olsun ki, bütün boş hüceyrələri domino daşları ilə doldurmaq mümkün olmasın.

Bir tam ədəd min(x, 10^6) çıxarın.