2295 - 【NOIP2019】D2T1 Emiya 家今天的饭
时间限制 : 1 秒
内存限制 : 256 MB
输入
第 1 行两个用单个空格隔开的整数 n, m。
第 2 行至第 n + 1 行，每行 m 个用单个空格隔开的整数，其中第 i + 1 行的 m 个数依次为 ai,1, ai,2, . . . , ai,m。
输出
仅一行一个整数，表示所求方案数对 998, 244, 353 取模的结果。
样例
输入
2 3 1 0 1 0 1 1
输出
3
输入
3 3 1 2 3 4 5 0 6 0 0
输出
190
输入
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
提示
【样例 1 解释】
由于在这个样例中，对于每组 i, j，Emiya 都最多只会做一道菜，因此我们直接通 过给出烹饪方法、主要食材的编号来描述一道菜。
符合要求的方案包括：
- 做一道用烹饪方法 1、主要食材 1 的菜和一道用烹饪方法 2、主要食材 2 的菜
- 做一道用烹饪方法 1、主要食材 1 的菜和一道用烹饪方法 2、主要食材 3 的菜
- 做一道用烹饪方法 1、主要食材 3 的菜和一道用烹饪方法 2、主要食材 2 的菜
因此输出结果为 3 mod 998, 244, 353 = 3。
需要注意的是，所有只包含一道菜的方案都是不符合要求的，因为唯一的主要食材在超过一半的菜中出现，这不满足 Yazid 的要求。
【样例 2 解释】
Emiya 必须至少做 2 道菜。
做 2 道菜的符合要求的方案数为 100。
做 3 道菜的符合要求的方案数为 90。
此符合要求的方案数为 100 + 90 = 190。
【数据范围】 