E or m

题目描述

我们有一个 $N$ 行 $M$ 列的网格 $A$。初始时，每个方格上都写着 $0$。

接下来执行以下操作。

• 对每个满足 $1 \le i \le N$ 的整数 $i$，在第 $i$ 行中，把最左侧的零个或多个方格中的数字改为 $1$。
• 对每个满足 $1 \le j \le M$ 的整数 $j$，在第 $j$ 列中，把最上方的零个或多个方格中的数字改为 $1$。

设 $S$ 为可以通过这种方式得到的网格的集合。

给你一个由 0、1、? 组成的 $N$ 行 $M$ 列的网格 $X$。 把每个 ? 替换成 0 或 1，共可以得到 $2^q$ 个网格，其中 $q$ 是 $X$ 中 ? 的个数。问其中有多少个属于 $S$？ 这个数量可能非常巨大，请对 $998244353$ 取模。

输入格式

输入按以下格式从标准输入给出：

$N$ $M$
$X_{1,1}$ $X_{1,2}$ $\dots$ $X_{1,M}$
$X_{2,1}$ $X_{2,2}$ $\dots$ $X_{2,M}$
$\vdots$
$X_{N,1}$ $X_{N,2}$ $\dots$ $X_{N,M}$

输出格式

输出一个整数，表示答案。

样例

2 3
0?1
?1?

6

以下六个网格属于 $S$。

011  011  001
010  011  110

001  011  011
111  110  111

5 3
101
010
101
010
101

0

$X$ 中可能没有 ?，答案也可能为 $0$。

18 18
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????

462237431

请务必对 $998244353$ 取模后输出。

数据范围

• $N$ 和 $M$ 是整数。
• $1 \le N,M \le 18$
• $X$ 是由 0、1、? 组成的 $N$ 行 $M$ 列的网格。