← 返回题目列表

Codeforces · 578/F

F. 镜盒

中文机器翻译题面 查看原题

你得到了一个装满镜子的盒子。盒子由大小为 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。