CF115C.Plumber

Little John aspires to become a plumber! Today he has drawn a grid consisting of n rows and m columns, consisting of n × m square cells.

In each cell he will draw a pipe segment. He can only draw four types of segments numbered from 1 to 4, illustrated as follows:

Each pipe segment has two ends, illustrated by the arrows in the picture above. For example, segment 1 has ends at top and left side of it.

Little John considers the piping system to be leaking if there is at least one pipe segment inside the grid whose end is not connected to another pipe's end or to the border of the grid. The image below shows an example of leaking and non-leaking systems of size 1 × 2.

Now, you will be given the grid that has been partially filled by Little John. Each cell will either contain one of the four segments above, or be empty. Find the number of possible different non-leaking final systems after Little John finishes filling all of the empty cells with pipe segments. Print this number modulo 1000003 (106 + 3).

Note that rotations or flipping of the grid are not allowed and so two configurations that are identical only when one of them has been rotated or flipped either horizontally or vertically are considered two different configurations.

小约翰立志成为一名管道工！今天，他画出了一个由 $n$ 行和 $m$ 列组成的网格，共包含 $n \times m$ 个正方形格子。

在每个格子中，他将绘制一段管道。他只能绘制如下图所示的四种类型的管道段，编号为 1 至 4：

每段管道有两个端口，如上图箭头所示。例如，第 1 类管道段的两个端口分别位于其顶部和左侧。

小约翰认为该管道系统存在泄漏，当且仅当网格中至少存在一段管道，其某个端口既未连接到另一段管道的端口，也未连接到网格边界。下图展示了一个 $1 \times 2$ 尺寸的泄漏系统与非泄漏系统的示例：

现在，你将获得一个已被小约翰部分填充的网格。每个格子要么已填入上述四种管道段之一，要么为空。请计算：在小约翰将所有空格子均填入管道段后，能形成多少种互不相同的、无泄漏的完整管道系统？结果对 $1000003$（即 $10^6 + 3$）取模后输出。

注意：不允许旋转或翻转整个网格；因此，若两种构型仅在水平或垂直翻转、或任意角度旋转后才相同，则仍视为两种不同的构型。

The first line will contain two single-space separated integers n and m (1 ≤ n, m, n·m ≤ 5·105) — the number of rows and columns respectively. Then n lines follow, each contains exactly m characters — the description of the grid. Each character describes a cell and is either one of these:

• "1" - "4" — a pipe segment of one of four types as described above
• "." — an empty cell

第一行包含两个以单个空格分隔的整数 $n$ 和 $m$（$1 \leq n, m, n\cdot m \leq 5\cdot 10^5$），分别表示网格的行数和列数。随后是 $n$ 行，每行恰好包含 $m$ 个字符——描述该网格。每个字符描述一个单元格，且为以下之一：

• "1" – "4" —— 上述四种类型之一的管道片段
• "." —— 空单元格

Print a single integer denoting the number of possible final non-leaking pipe systems modulo 1000003 (106 + 3). If there are no such configurations, print 0.

输出一个整数，表示模 $1000003$（即 $10^6 + 3$）意义下可能的最终不漏气管道系统的数量。若不存在这样的构型，则输出 $0$。

For the first example, the initial configuration of the grid is as follows.

The only two possible final non-leaking pipe configurations are as follows:

For the second example, the initial grid is already leaking, so there will be no final grid that is non-leaking.

For the final example, there's only one possible non-leaking final grid as follows.

对于第一个例子，网格的初始配置如下所示。

唯一两种可能的最终不漏水管道配置如下：

对于第二个例子，初始网格已经漏水，因此不存在任何不漏水的最终网格。

对于最后一个例子，仅存在一种可能的不漏水最终网格，如下所示。