小约翰渴望成为一名水管工!今天他画了一个n行m列的网格,由n×m个方格组成。
在每个单元格中,他将绘制一段管道。他只能画出四种类型的线段,编号为1到4,如下所示:
每个管段都有两端,如上图中的箭头所示。例如,线段 1 的端点位于其顶部和左侧。
如果网格内至少有一个管道段的末端未连接到另一管道的末端或网格的边界,则小约翰认为管道系统发生泄漏。下图显示了尺寸为 1 × 2 的泄漏和非泄漏系统的示例。
现在,您将看到已被小约翰部分填充的网格。每个单元格要么包含上述四个段之一,要么为空。在小约翰用管段填充完所有空单元后,求出可能的不同不泄漏最终系统的数量。打印该数字以 1000003 (106 + 3) 为模。
请注意,不允许旋转或翻转网格,因此仅当其中一个配置水平或垂直旋转或翻转时才相同的两个配置被视为两种不同的配置。
输入
第一行将包含两个单空格分隔的整数 n 和 m (1 ≤ n, m, n·m ≤ 5·105) — 分别是行数和列数。接下来是 n 行,每行恰好包含 m 个字符——网格的描述。每个字符描述一个单元格,并且是以下之一:
- "1" - "4" — 上述四种类型之一的管段
- “。” — 一个空单元格
输出
打印一个整数,表示最终可能的无泄漏管道系统的数量以 1000003 (106 + 3) 为模。如果没有这样的配置,则打印0。
示例
输入 #1
2 2 13 ..
输出 #1
2
输入 #2
3 1 1 4 .
输出 #2
0
输入 #3
2 2 3. .1
输出 #3
1
注意
对于第一个示例,网格的初始配置如下。
仅有的两种可能的最终无泄漏管道配置如下:
对于第二个示例,初始网格已经泄漏,因此将不存在非泄漏的最终网格。
对于最后一个示例,只有一个可能的非泄漏最终网格,如下所示。