U560777 「菈菈」的导线

「菈菈」现在需要给一些方格摆导线。

有 $n$ 行 $m$ 列的方格，需要在一些地方摆放导线（**要求摆的地方必须摆，不要求摆的地方禁止摆**）。 允许摆放六种导线：上下相连、左右相连、左上相连、左下相连、右上相连、右下相连。  例如，以上的摆法是一种合法的方案 问有多少种摆法使得摆出来的导线没有断路（允许形成多个回路）。 答案对 $998244353$ 取模。 本题有两个 $Subtask$ : #### Subtask 1 $2 \leq n，m \leq 20$ #### Subtask 2 $2 \leq n \leq 10^{1000000}，2 \leq m \leq 6$ （输入方式比较特别，见“输入格式”）

- 先输入一个整数 $T∈\{1,2\}$ 表示 $Subtask$ 。 #### 对于 $Subtask 1$ - 一行两个整数 $n,m$ 。 - 接下来一个 $n$ 行 $m$ 列的 $0/1$ 表示某个位置是否要求摆放导线。 #### 对于 $Subtask 2$ - 一行四个整数 $w,k,r,m$ 含义见下文。 由于 $n$ 太大，每一个位置是否需要放置导线无法输入，将会按照以下方式给出： 首先设 $n=w\times k+r$ 其中 $0\leq r

一个整数表示方案数 对 $998244353$ 取模

本题的全部输入均为非负整数 #### Subtask 1 时间限制 $2s$ 占含全部测试点的 $40\%$ 在 $Subtask 1$ 的测试点中： 对于 $100\%$ 的数据有 $2 \leq n，m \leq 20$ - 对于 $10\%$ 的数据有 $2 \leq n，m \leq 5$ - 对于 $40\%$ 的数据有 $2 \leq n，m \leq 10$ - 对于 $60\%$ 的数据有 $2 \leq n，m \leq 18$ #### Subtask 2 时间限制 $300ms$ 占含全部测试点的 $60\%$ 在 $Subtask 2$ 的测试点中： 对于 $100\%$ 的数据有 $2 \leq w\times k+r \leq 10^{1000000}，2 \leq m \leq 6，1 \leq k \leq 10^3$ - 对于 $20\%$ 的数据有 $2 \leq w\times k+r \leq 10^3，2 \leq m \leq 6，w=1，r=0$ - 对于 $40\%$ 的数据有 $2 \leq w\times k+r \leq 2\times 10^4，2 \leq m \leq 6，1 \leq k \leq 10^3$ - 对于 $60\%$ 的数据有 $2 \leq w\times k+r \leq 10^{18}，2 \leq m \leq 6，1 \leq k \leq 10^3$ - 对于另外 $20\%$ 的数据有 $2 \leq w\times k+r \leq 10^{1000000}，2 \leq m \leq 6，1 \leq k=1$