Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:512 MB
Statistics

题目描述

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

下发文件