#P18661. LaLa and Magic Stone
LaLa and Magic Stone
LaLa and Magic Stone
一天,拉拉发现魔法工具使用的魔法石部件用完了。你可以把这种部件理解为我们世界中的电池。她赶紧去附近的商店买了一整块魔法石。
拉拉想把这块魔法石切成部件。石板由 N×M 个小格构成,其中有些格子不适合她的魔法工具使用。
需要的部件是由 7 个小格组成的 U 形,形状如下。允许对该形状作90度整数倍旋转。

拉拉忘了购买魔法石胶水,因此不能把切下来的更小碎片粘起来组成所需形状。她也不愿浪费魔法石:当且仅当每一个可用格都属于一个所需形状的部件时,她才满意。每个部件仅包含可用格,不同部件不能重叠。
请计算让拉拉满意的切割方案数,答案对 998244353 取模。两个方案不同,当且仅当存在两个可用格,它们在一个方案里属于同一个部件,在另一个方案里属于不同部件。
输入格式
单组输入,格式为:
N M
S0
S1
...
S(N-1)
N 为行数,M 为列数。每个 Si 是长度为 M 的二进制字符串。从上到下、从左到右分别以0为起点编号;Si 的第 j 个字符为 1 当且仅当格子(i,j)不可用,为 0 则表示可用。
所有输入满足:N、M 为整数,3≤N,M≤1000。
输出格式
输出一个整数,表示满足要求的切割方案数对998244353取模的结果。
样例输入 1
4 4
0001
0000
0000
1000
样例输出 1
2
样例输入 2
5 4
0001
0101
0000
1010
1000
样例输出 2
1
样例说明
第一组样例的两种切割方式如下(原PDF插图):


第二组样例唯一的切割方式如下(原PDF插图):
