CF578F Mirror Box
题目描述
你有一个装满镜子的盒子。盒子由一个 $n \times m$ 的网格组成。网格的每个单元格里都装有一面镜子，这面镜子的形状要么是 ‘$\backslash$’，要么是 ‘$/$’（即与水平线或垂直线成 $45$ 度角）。但有些单元格中的镜子被损坏了。你需要在这些空格中重新放入新的镜子，使得满足以下两个条件：
1. 如果你将一束光线从任意边界单元格边中的任意单位线段的中点，沿水平方向或垂直方向射入盒子，那么光线会从你射入的那个单位线段相邻的那个单位线段穿出盒子。
2. 镜盒网格中的每一个单位线段，都能够被至少一束以水平方向或垂直方向射入盒子（按照前面规则）而贯穿的光线穿过。
你在尝试放置镜子后发现，有很多种放置新镜子的方式。请你计算有多少种不同的放置方法？由于答案可能非常大，请输出对质数 $MOD$ 取模后的值。
输入格式
第一行包含三个整数 $n$、$m$、$MOD$（$1\leq n,m\leq100$，$3\leq MOD\leq 10^9+7$，$MOD$ 为质数），$m$ 和 $n$ 表示盒子的尺寸，$MOD$ 表示取模的质数。
接下来的 $n$ 行中，每行一个长度为 $m$ 的字符串。每个字符串仅包含 ‘$/$’、‘$\backslash$’ 和 ‘*’，其中 ‘*’ 表示该格子的镜子被破坏了。
保证 ‘*’ 的数量不超过 $200$。
输出格式
输出答案对 $MOD$ 取模后的结果。
说明/提示
样例 1 唯一的放法如题面左图所示。
样例 2 唯一的放法如题面右图所示。
对于第三个样例，有 $5$ 种可能性，具体如下：
1.
2.
3.
4.
5.
答案对 $3$ 取模，输出应为 $2$。
由 ChatGPT 5 翻译