Hệ thống ống nước

An đang tập làm thợ sửa ống nước. Cậu vẽ một lưới gồm $n$ hàng và $m$ cột, mỗi ô của lưới sẽ chứa đúng một đoạn ống.

Có $4$ loại đoạn ống, đánh số từ $1$ đến $4$. Mỗi đoạn ống có đúng hai đầu ống, nằm ở hai cạnh khác nhau của ô chứa nó:

• Loại $1$: đầu ống ở cạnh trên và cạnh trái.
• Loại $2$: đầu ống ở cạnh dưới và cạnh trái.
• Loại $3$: đầu ống ở cạnh dưới và cạnh phải.
• Loại $4$: đầu ống ở cạnh trên và cạnh phải.

Như vậy mỗi đoạn ống luôn có đúng một đầu nằm ở cạnh trên hoặc cạnh dưới, và đúng một đầu nằm ở cạnh trái hoặc cạnh phải.

Hệ thống ống bị rò rỉ nếu có ít nhất một đầu ống không nối được vào đầu ống nào khác và cũng không nằm trên biên của lưới. Cụ thể, với hai ô kề nhau theo chiều ngang, ô bên trái có đầu ống ở cạnh phải khi và chỉ khi ô bên phải có đầu ống ở cạnh trái; tương tự, với hai ô kề nhau theo chiều dọc, ô phía trên có đầu ống ở cạnh dưới khi và chỉ khi ô phía dưới có đầu ống ở cạnh trên. Đầu ống nằm trên biên của lưới luôn được chấp nhận.

An đã điền sẵn một số ô, các ô còn lại vẫn đang trống. Hãy đếm số cách điền tất cả các ô trống (mỗi ô nhận một trong $4$ loại đoạn ống) sao cho hệ thống thu được không bị rò rỉ, rồi in kết quả theo modulo $1000003$.

Hai cách điền là khác nhau nếu tồn tại một ô mà loại đoạn ống đặt tại đó khác nhau. Phép quay hay lật lưới không được tính, tức là hai cấu hình chỉ trùng nhau sau khi quay hoặc lật vẫn được coi là khác nhau.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $n$ và $m$: số hàng và số cột của lưới.
• $n$ dòng tiếp theo, mỗi dòng chứa đúng $m$ ký tự mô tả một hàng của lưới. Ký tự là 1, 2, 3, 4 nếu ô đó đã được đặt đoạn ống loại tương ứng, hoặc . nếu ô đó còn trống.

Dữ liệu ra

In ra một số nguyên duy nhất: số cách điền hợp lệ theo modulo $1000003$. Nếu không tồn tại cách nào, in ra $0$.

Ràng buộc

• $1\le n$, $1\le m$, $n·m\le 5·{10}^5$
• Mỗi ký tự của lưới thuộc tập $\{$1, 2, 3, 4, .$\}$

Ví dụ