P5347 【XR-1】俄罗斯方块

小粉兔最近沉迷一个名叫“俄罗斯方块”的游戏。 然而本题除了都有格子和颜色之外和俄罗斯方块没什么关系。

有一个 $n \times m$ 的方格图，小粉兔打算在其中画线。 他可以画线若干次，也可以不画。每次画线必须从一个没有被画过的方格中心开始。 只能往上下左右四个方向画线，对应方向上的方格记作**目标方格**。 目标方格能被画，当且仅当下面三种情况： 1. 如果目标方格**没有被画过**，则可以经过两个方格公共边的中点，直接画到目标方格中心，此时**可以选择**结束本次画线； 2. 如果目标方格**已经被画过**，且这条画过的线是**贯穿整个方格的线**，则可以再画一条与这条线**垂直**的**贯穿整个方格的线**。对**贯穿整个方格的线**的定义为：这条线在方格中**没有改变方向**，**上下贯穿**或**左右贯穿**； 3. 如果目标方格是本次画线的**起笔方格**，则可以经过两个方格公共边的中点，直接画到目标方格中心，此时**必须**结束本次画线。 当然，不能画到整个方格图外面去。 虽然小粉兔制定了如此严苛的规则，但是他仍然有很多种颜色的笔，每次画线他可以选择 $c$ 种颜色中的任意一种用来画线。 不幸的是，方格图中有一些位置坏掉了，不能被经过，即在任意一次画线中不能画到坏掉的位置上。 小粉兔想知道，在这些限制下，最终能画出多少种本质不同的图呢？ 小粉兔不想要求太多，当 $\mathrm{op}=0$ 时，两张图本质相同当且仅当不考虑坏掉的方格，它们看起来相同（每个位置上的线条方向和颜色均相同）。 而当 $\mathrm{op}=1$ 时，两张图本质相同当且仅当不考虑坏掉的方格，它们看起来相同，或旋转 $180 ^ {\circ}$ 后看起来相同。 因为答案可能很多，所以小粉兔只想知道答案对 $998244353$ 取模的结果。

无

无

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