你得到了一个装满镜子的盒子。盒子由大小为 n × m 的网格组成。网格的每个单元格都包含一个形状为“\”或“/”(与水平线或垂直线成45度)的镜子。但一些牢房中的镜子已被破坏。您希望将新的镜像放入这些网格中,以便满足以下两个条件:
1. 如果您将光线水平/垂直放置到位于某个边界单元一侧的任何单位段的中间,则光线将从相邻单位段射出到您放置光线的段。
2.镜盒网格的每个单元段可以被至少一条光线穿过,按照上一段的规则水平/垂直放入盒内
当你尝试放置一些镜子后,你会发现有很多方法可以做到这一点。有多少种可能的方法?答案可能很大,所以请求出对素数模 MOD 的结果。
输入
第一行包含三个整数 n、m、MOD(1 ≤ n、m ≤ 100、3 ≤ MOD ≤ 109 + 7,MOD 为素数),m、n 表示盒子的尺寸,MOD 是对答案取模的数字。
以下 n 行每行包含一个长度为 m 的字符串。每个字符串仅包含“/”、“\”、“*”,其中“*”表示该网格中的镜像已被破坏。
保证“*”的个数不超过200个。
输出
输出对 MOD 取模的答案。
示例
输入 #1
2 2 1000000007 */ /*
输出 #1
1
输入 #2
2 2 1000000007 ** \\
输出 #2
1
输入 #3
2 2 3 ** **
输出 #3
2
注意
示例 1 的唯一方法如声明中的左图所示。
示例 2 的唯一方法如声明中的右图所示。
对于第三个样本,有以下 5 种可能性:
1.
$$\mathrm{~W~}$$
$$\mathrm{~V~}$$
2.
$$\sqrt{2}$$
$$\mathrm{~V~}$$
3.
$$\Delta$$
$$\sqrt{2}$$
4.
$$\Delta$$
$$\mathrm{~W~}$$
5.
$$\mathrm{~V~}$$
$$\Delta$$
答案是 3 模,所以输出应该是 2。