日本料理
时间限制： 1 秒
内存限制： 256 MB
输入： 标准输入
输出： 标准输出
题目描述
日本有大量传统烹饪方式来处理相同的食材。假设共有 $n$ 种不同的烹饪方式，编号从 $1$ 到 $n$，以及 $m$ 种传统食材，编号从 $1$ 到 $m$。
一位著名厨师举办大师班，计划使用第 $i$ 种烹饪方式和第 $j$ 种作为主要食材，恰好制作 $a_{i, j}$ 道菜。因此，制作的总菜品数为 $A = \sum_{i=1}^n \sum_{j=1}^m a_{i, j}$。
两位著名的美食评论家计划参加大师班，厨师提前计划从中选择 $k$ 道菜供他们品尝。当然，评论家们对所选菜品的集合有严格的要求：
- 集合必须非空，即至少提供一道菜，$k \ge 1$；
- 集合中的所有菜品必须使用互不相同的烹饪方式；
- 以同一食材为主要食材的菜品不得超过一半，即对于任意食材，以其为主的菜品数量不超过 $\lfloor k/2\rfloor$。
厨师想知道，从 $A$ 道菜中选出任意大小的满足评论家要求的集合有多少种不同的方式？如果两个集合中存在至少一道菜不同，则认为它们不同。由于答案可能很大，输出模 $998\,244\,353$ 的结果。
输入数据
第一行包含两个整数 $n$ 和 $m$ —— 烹饪方式的数量和传统食材的数量（$1 \le n \le 100$；$1 \le m \le 2000$）。
接下来的 $n$ 行中，第 $i$ 行包含 $m$ 个整数 $a_{i, j}$ —— 使用第 $i$ 种烹饪方式和第 $j$ 种食材可以制作的菜品数量（$0 \le a_{i,j} \le 998\,244\,353$）。
输出数据
输出一个整数 —— 满足评论家要求的菜品集合数量模 $998\,244\,353$ 的结果。
评分系统
仅当子任务及其所需子任务的所有测试均通过时，该子任务才得分。
| 子任务 | 分值 | $n = $ | $m = $ | $a_{i,j} < $ | 必须的子任务 | 评测信息 |
|---|---|---|---|---|---|---|
| 0 | – | 样例 | 无 | 无 | 无 | 完全 |
| 1 | 4 | $2$ | $2$ | $2$ | 无 | 首次错误 |
| 2 | 4 | $2$ | $3$ | $2$ | 1 | 首次错误 |
| 3 | 4 | $5$ | $2$ | $2$ | 1 | 首次错误 |
| 4 | 4 | $5$ | $3$ | $2$ | 1 – 3 | 首次错误 |
| 5 | 4 | $10$ | $2$ | $2$ | 1, 3 | 首次错误 |
| 6 | 4 | $10$ | $3$ | $2$ | 1 – 5 | 首次错误 |
| 7 | 4 | $10$ | $2$ | $1000$ | 1, 3, 5 | 首次错误 |
| 8 | 4 | $10$ | $3$ | $1000$ | 1 – 7 | 首次错误 |
| 9 | 16 | $40$ | $2$ | $1000$ | 1, 3, 5, 7 | 首次错误 |
| 10 | 16 | $40$ | $3$ | $1000$ | 1 – 9 | 首次错误 |
| 11 | 20 | $40$ | $500$ | $1000$ | 0 – 10 | 首次错误 |
| 12 | 16 | $100$ | $2000$ | $998\,244\,353$ | 0 – 11 | 首次错误 |
示例
示例 1
输入
2 3
1 0 1
0 1 1输出
3示例 2
输入
3 3
1 2 3
4 5 0
6 0 0输出
190示例 3
输入
5 5
1 0 0 1 1
0 1 0 1 0
1 1 1 1 0
1 0 1 0 1
0 1 1 0 1输出
742