← 返回题目列表

AtCoder · abc295_h

Ex. E 或 m

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

我们有一个网格 A 与 N 行和 M 列。最初, 每个方格上都写有 0 。
让我们执行以下操作。

  • 对于每个整数 i 这样 1 \le i \le N,在 i-第行,将零个或多个最左边方格中的数字变成 1.
  • 对于每个整数 j 这样 1 \le j \le M,在 j第列,将零个或多个最上面的方格中的数字转换为 1.

让 S 是可以通过这种方式获得的网格的集合。

给你一个网格 X 与 N 行和 M 列组成 0, 1,和 ?.
有 2^q 可以通过替换每个网格来获得 ? 与 0 or 1,其中 q 是数量 ? in X。其中有多少人在 S?
这个计数可能很大,所以求它的模 998244353.

约束

  • N 和 M 是整数。
  • 1 \le N,M \le 18
  • X 是一个网格 N 行和 M 列组成 0, 1,和 ?.

输入

输入由标准输入按以下格式给出:

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}

输出

打印一个代表答案的整数。


示例输入 1

2 3
0?1
?1?

示例输出 1

6

以下六格在 S.

011  011  001
010  011  110

001  011  011
111  110  111

示例输入 2

5 3
101
010
101
010
101

示例输出 2

0

X 可能没有 ?,答案可能是 0.


示例输入 3

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

示例输出 3

462237431

一定要找到计数模数 998244353.