题目背景

小粉兔最近沉迷一个名叫“俄罗斯方块”的游戏。

然而本题除了都有格子和颜色之外和俄罗斯方块没什么关系。

题目描述

有一个 $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 3 2 0
...

7

1 3 2 1
...

5

2 2 1 0
..
..

16

2 2 1 1
..
..

10

2 2 1 0
..
#.

4

4 5 1 0
.....
.#.#.
....#
.#...

65856

4 5 1 1
.....
.#.#.
....#
.#...

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\}$。