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 1000003.

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 1000003.

Restricții și precizări

• 1 ≤ N ≤ 1000
• 1 ≤ M ≤ 1000
• 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.