题目描述
泠洛有一块 $n\times m$ 的木板，她在上面摆放了若干个 L 型卡片。我们可以将木板看成一个 $n\times m$ 的矩阵，一个 L 型卡片看成三个方格组成的连通块，使得连通块形态为 L 型（可以旋转）。固定这些卡片需要用图钉钉在 L 的中心，因此木板上 L 中心位置会钻出一个洞。（L 的中心即 L 的拐角位置）
下面是四种 L 型连通块可能的形态：（$1,2$ 代表在连通块内的方格，$2$ 代表 L 的中心）
01 10 12 21
12 21 01 10一个月后，泠洛偶然看到了当初钉卡片的木板。她想知道，有多少种摆放卡片的方式符合这些洞的分布。由于答案过大，你只需告诉她答案对 $998244353$ 取模后的结果即可。
输入格式
共有 $T$ 组数据，每组数据开头有两个正整数 $n,m$。
接下来 $n$ 行，每行一个长度为 $m$ 的 01 串，表示这一行每个位置是否有洞。（$1$ 代表有，$0$ 代表没有）
输出格式
共 $T$ 行，每一行一个非负整数表示答案对 $998244353$ 取模后的结果。
样例
样例 1 输入
2
4 4
0000
0110
0110
0000
9 9
000010101
000000000
000000000
000000000
000000000
000000001
000001000
000000000
000000001样例 1 输出
1
8样例 2 输入
见下发文件。
样例 2 输出
见下发文件。
数据范围
对于所有数据，$\sum n\times m\leqslant 3\times 10^6,T\leqslant 3\times10^5$。
| 数据点编号 | $\sum n\times m\leqslant$ | 特殊性质 |
|---|---|---|
| $1$ | $300$ | A |
| $2$ | $300$ | |
| $3$ | $300$ | |
| $4$ | BCD | |
| $5$ | B | |
| $6$ | D | |
| $7$ | $3\times 10^5$ | |
| $8$ | ||
| $9$ | ||
| $10$ |
特殊性质 A：保证 $1$ 的数量之和不超过 $10$。
特殊性质 B：保证有解。
特殊性质 C：保证 $1$ 数量为 $\frac{nm}3$。
特殊性质 D：保证 $1$ 不相邻。