【XR-1】俄罗斯方块
题目背景
小粉兔最近沉迷一个名叫“俄罗斯方块”的游戏。
然而本题除了都有格子和颜色之外和俄罗斯方块没什么关系。
题目描述
有一个 $n \times m$ 的方格图，小粉兔打算在其中画线。
他可以画线若干次，也可以不画。每次画线必须从一个没有被画过的方格中心开始。
只能往上下左右四个方向画线，对应方向上的方格记作**目标方格**。
目标方格能被画，当且仅当下面三种情况：
1. 如果目标方格**没有被画过**，则可以经过两个方格公共边的中点，直接画到目标方格中心，此时**可以选择**结束本次画线；
2. 如果目标方格**已经被画过**，且这条画过的线是**贯穿整个方格的线**，则可以再画一条与这条线**垂直**的**贯穿整个方格的线**。对**贯穿整个方格的线**的定义为：这条线在方格中**没有改变方向**，**上下贯穿**或**左右贯穿**；
3. 如果目标方格是本次画线的**起笔方格**，则可以经过两个方格公共边的中点，直接画到目标方格中心，此时**必须**结束本次画线。
当然，不能画到整个方格图外面去。
虽然小粉兔制定了如此严苛的规则，但是他仍然有很多种颜色的笔，每次画线他可以选择 $c$ 种颜色中的任意一种用来画线。
不幸的是，方格图中有一些位置坏掉了，不能被经过，即在任意一次画线中不能画到坏掉的位置上。
小粉兔想知道，在这些限制下，最终能画出多少种本质不同的图呢？
小粉兔不想要求太多，当 $\mathrm{op}=0$ 时，两张图本质相同当且仅当不考虑坏掉的方格，它们看起来相同（每个位置上的线条方向和颜色均相同）。
而当 $\mathrm{op}=1$ 时，两张图本质相同当且仅当不考虑坏掉的方格，它们看起来相同，或旋转 $180 ^ {\circ}$ 后看起来相同。
因为答案可能很多，所以小粉兔只想知道答案对 $998244353$ 取模的结果。
输入输出格式
输入格式
第一行三个正整数 $n,m,c$ 和一个非 $0$ 即 $1$ 的数 $\mathrm{op}$。
接下来 $n$ 行，每行一个长度为 $m$ 的字符串，只包含 `.` 和 `#` 两种字符，描述方格图的情况。如果第 $i$ 行的第 $j$ 个字符为 `#` 则表示方格图中第 $i$ 行第 $j$ 列的方格坏掉了，否则没有坏掉。
输出格式
输出一行一个数，表示答案对 $998244353$ 取模的结果。
输入输出样例
输入样例 #1
1 3 2 0
...
输出样例 #1
7
输入样例 #2
1 3 2 1
...
输出样例 #2
5
输入样例 #3
2 2 1 0
..
..
输出样例 #3
16
输入样例 #4
2 2 1 1
..
..
输出样例 #4
10
输入样例 #5
2 2 1 0
..
#.
输出样例 #5
4
输入样例 #6
4 5 1 0
.....
.#.#.
....#
.#...
输出样例 #6
65856
输入样例 #7
4 5 1 1
.....
.#.#.
....#
.#...
输出样例 #7
65616
说明
【样例 $1$ 说明】
共有如下 $7$ 种本质不同的图：
【样例 $6$ 说明】
下面给出两种本质不同的图：
【数据规模与约定】
本题采用捆绑测试：
Subtask 1（12 points）：$n=1$，$\mathrm{op}=0$，没有坏掉的格子。
Subtask 2（13 points）：$c=1$，$\mathrm{op}=0$。
Subtask 3（12 points）：$c=1$，$\mathrm{op}=1$。
Subtask 4（14 points）：$m\le 5$，$\mathrm{op}=0$。
Subtask 5（25 points）：$\mathrm{op}=0$。
Subtask 6（8 points）：$n\bmod 2=0$，$\mathrm{op}=1$。
Subtask 7（8 points）：$n\bmod 2=1$，$m\bmod 2=0$，$\mathrm{op}=1$。
Subtask 8（8 points）：$n\bmod 2=1$，$m\bmod 2=1$，$\mathrm{op}=1$。
对于 $100\%$ 的数据，$1\le n,m\le 9$，$1\le c\le 10^6$，$\mathrm{op}\in\{0,1\}$。