C1565 【XR-1】俄罗斯方块

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

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

有一个 $n \times m$ 的方格图，小粉兔打算在其中画线。

他可以画线若干次，也可以不画。每次画线必须从一个没有被画过的方格中心开始。

只能往上下左右四个方向画线，对应方向上的方格记作目标方格。

目标方格能被画，当且仅当下面三种情况：

1. 如果目标方格没有被画过，则可以经过两个方格公共边的中点，直接画到目标方格中心，此时可以选择结束本次画线；
2. 如果目标方格已经被画过，且这条画过的线是贯穿整个方格的线，则可以再画一条与这条线垂直的贯穿整个方格的线。对贯穿整个方格的线的定义为：这条线在方格中没有改变方向，上下贯穿或左右贯穿；
3. 如果目标方格是本次画线的起笔方格，则可以经过两个方格公共边的中点，直接画到目标方格中心，此时必须结束本次画线。

当然，不能画到整个方格图外面去。

虽然小粉兔制定了如此严苛的规则，但是他仍然有很多种颜色的笔，每次画线他可以选择 $c$ 种颜色中的任意一种用来画线。

不幸的是，方格图中有一些位置坏掉了，不能被经过，即在任意一次画线中不能画到坏掉的位置上。

小粉兔想知道，在这些限制下，最终能画出多少种本质不同的图呢？

小粉兔不想要求太多，当 $\mathrm{op}=0$ 时，两张图本质相同当且仅当不考虑坏掉的方格，它们看起来相同（每个位置上的线条方向和颜色均相同）。

而当 $\mathrm{op}=1$ 时，两张图本质相同当且仅当不考虑坏掉的方格，它们看起来相同，或旋转 $180 ^ {\circ}$ 后看起来相同。

因为答案可能很多，所以小粉兔只想知道答案对 $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