有一天，LaLa 发现她的魔法工具缺少魔法石组件（可以把它们想象成我们世界里的电池）。于是，LaLa 冲到附近的一家商店买了一块魔法石板。

LaLa 想要把这块石板切割成魔法石组件。石板由 $N \times M$ 个单元格组成。不幸的是，有些单元格与 LaLa 的魔法工具不兼容。

所需的魔法石组件是一个 7 单元格的 U 型件。

由于 LaLa 忘了买魔法石胶水，她无法将较小的碎片合并成所需的形状。此外，由于 LaLa 讨厌浪费魔法石，她只有在石板被切割成使得每一个兼容的单元格都属于一个所需的形状时才会感到满意。

编写一个程序，计算使得 LaLa 满意的切割石板的方法数，结果对 $998\,244\,353$ 取模。如果存在两个兼容的单元格，使得它们在一种切割方式中属于同一个组件，而在另一种切割方式中属于不同的组件，则这两种切割方式被认为是不同的。

输入格式

输入格式如下：

$N \ M$ $S_0$ $S_1$ $\vdots$ $S_{N-1}$

其中 $N$ 是石板的行数，$M$ 是列数，$S_i$ 是一个长度为 $M$ 的二进制字符串，如果第 $i$ 行（从上往下数）第 $j$ 列（从左往右数）的单元格是不兼容的，则第 $j$ 个字符为 '1'，否则为 '0'。

输入满足以下约束： $N$ 和 $M$ 为整数。 $3 \le N, M \le 1\,000$

输出格式

输出一个整数，表示使得 LaLa 满意的切割石板的方法数，对 $998\,244\,353$ 取模。

样例

输入格式 1

4 4
0001
0000
0000
1000

输出格式 1

2

说明

下图展示了第一个样例中两种可能的切割方式。

输入格式 2

5 4
0001
0101
0000
1010
1000

输出格式 2

1

说明

下图展示了第二个样例中唯一的一种切割方式。