rooks

Se consideră o tablă de șah sub forma unei matrice cu $M$ linii si $N$ coloane conținând caracterele . si #. Celulele care conțin # sunt considerate interzise și nu se pot așeza turnuri în ele. Celulele interzise nu blochează atacurile turnurilor.

Cerința

Să se calculeze $X$, numărul de posibilități de a așeza turnuri în celulele neinterzise, astfel încât să nu existe doua turnuri așezate pe aceeași linie sau pe aceeași coloana. Deoarece acest număr poate fi foarte mare, se va determina $X$ modulo $1 \ 000 \ 003$.

Date de intrare

Fișierul de intrare rooks.in conține pe prima linie numerele $M$ si $N$, iar pe fiecare dintre următoarele $M$ linii se afla câte $N$ caractere . sau #. Atenție, caracterele de pe o linie nu sunt separate prin spațiu.

Date de ieșire

Fișierul de ieșire rooks.out conține un singur număr natural, numărul $X$ modulo $1 \ 000 \ 003$.

Restricții și precizări

• $1 \leq M, N \leq 1 \ 000$;
• Vor exista cel mult $17$ celule interzise

Exemplu

rooks.in

3 3
..#
##.
#.#

rooks.out

10

Explicație

Este o soluție cu zero turnuri, sunt patru soluții cu un turn, patru soluții cu două turnuri si o soluție cu trei turnuri.