题目描述

小 John 立志成为一名水管工！今天他画了一张由 $n$ 行 $m$ 列组成的网格，共 $n \times m$ 个方块格。

他要在每个格子里画一段水管。他只能画 1 到 4 号的四种管段，示意如下：

每个管段有两个端点，即上图中的箭头。例如 1 号管段的两个端点在它的上边和左边。

John 认为管道系统是"漏水"的，当且仅当网格中至少有一个管段的某个端点没有与另一个管段的端点或网格边界相连。下图为一个 $1 \times 2$ 的漏水系统与不漏水系统的例子。

现在给你 John 已经部分填好的网格：每个格子要么已是上述四种管段之一，要么是空的。求 John 把所有空格子填满后，可能得到的不同"不漏水"最终系统的数量。把答案对 $10^6+3$ 取模（1000003）后输出。

注意：网格不允许旋转或翻转，因此两个仅通过水平/垂直旋转或翻转才相同的配置视为两个不同的配置。

输入格式

第一行包含两个用空格隔开的整数 $n$ 和 $m$（$1 \le n, m$，$n \cdot m \le 5 \cdot 10^5$），分别表示行数和列数。接下来 $n$ 行，每行恰好 $m$ 个字符——网格的描述。每个字符是以下之一：

• "1" - "4"——上述四种管段之一；
• "."——空格子。

输出格式

输出一个整数——填完全部空格子后可能得到的不同"不漏水"最终系统的数量，对 $10^6+3$ 取模（1000003）。若不存在这样的配置，输出 0。

2 2
13
..

2

3 1
1
4
.

0

2 2
3.
.1

1

说明/提示

第一组样例的初始网格配置如下：

仅有的两个可行的不漏水最终配置如下：

第二组样例中，初始网格已经是漏水的，所以不可能有任何不漏水的最终网格。

第三组样例中，唯一可行的不漏水最终网格如下：