题目描述
泠洛有一块 $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$ 不相邻。