P17412 【MX-X31-T6】「FAOI-R14」数据生成器（加强版）

本题为 [P17410 【MX-X31-T6】「FAOI-R14」数据生成器 ](https://www.luogu.com.cn/problem/P17410) 的加强版，唯一的区别是 $n,m$ 的范围。

小 A 给梦熊周赛出了一道题： > 给定两个整数序列 $a_1,a_2,\ldots,a_n$ 和 $b_1,b_2,\ldots,b_m$，以及一个元素均属于 $\{0,1,2\}$ 的 $n\times m$ 矩阵 $c$。 > > 对于 $c$ 中的每个 $2$，你需要将其替换为 $0$ 或 $1$；矩阵中原有的 $0$ 和 $1$ 保持不变。替换后得到一个 $01$ 矩阵 $d$。矩阵 $d$ 需要满足： > - 对于所有 $i\in[1,n]$，均有 $\sum_{j=1}^m d_{i,j} \ge a_i$； > - 对于所有 $j\in[1,m]$，均有 $\sum_{i=1}^n d_{i,j} \ge b_j$； > > 在所有满足上述条件的矩阵 $d$ 中，你需要最小化矩阵中 $1$ 的数量。 若矩阵 $d$ 满足上述条件，且不存在另一个满足上述条件、矩阵中 $1$ 的数量不超过它的矩阵，则称 $d$ 是原问题的唯一最优解。 小 A 是凉心出题人，最喜欢干的事就是脚造数据。小 A 首先选定正整数 $n,m$，以及一个 $n\times m$ 的集合矩阵 $S$；其中对于所有 $i\in[1,n]$，$j\in[1,m]$，均有 $S_{i,j}\subseteq\{0,1,2\}$ 且 $S_{i,j}\neq\varnothing$。 随后，小 A 按照以下方式相互独立地生成一份数据 $(a,b,c)$： - 对于所有 $i\in[1,n]$，从整数集合 $\{0,1,\ldots,m\}$ 中等概率选取 $a_i$； - 对于所有 $j\in[1,m]$，从整数集合 $\{0,1,\ldots,n\}$ 中等概率选取 $b_j$； - 对于所有 $i\in[1,n]$，$j\in[1,m]$，从集合 $S_{i,j}$ 中等概率选取 $c_{i,j}$。 因此，一共可能生成 $(m+1)^n(n+1)^m\prod_{i=1}^{n}\prod_{j=1}^{m}|S_{i,j}|$ 份不同的数据。 显然，原问题可能存在多个最优解，作为凉心出题人的小 A 自然不愿意编写 SPJ。不过考虑到梦熊周赛的题目出锅会被扣工资，小 A 还是想要知道不写 SPJ 也能正常评测的概率。 小 A 给你他的 $n,m$、集合矩阵 $S$，以及一个固定的 $n\times m$ 的 $01$ 矩阵 $h$。你需要求出所有可能的数据 $(a,b,c)$ 中，有多少份数据满足 $h$ 是原问题的唯一最优解。答案对 $998244353$ 取模。

第一行输入两个正整数 $n,m$，表示矩阵大小。 接下来 $n$ 行，第 $i$ 行一个长度为 $m$ 的字符串。设第 $i$ 行第 $j$ 个字符所表示的十进制整数为 $x$，其中 $1\le x\le 7$。对于每个 $y\in\{0,1,2\}$，$y\in S_{i,j}$ 当且仅当 $x$ 的二进制表示中从低到高第 $y$ 位为 $1$。 接下来 $n$ 行描述矩阵 $h$，每行包含一个长度为 $m$ 的 `01` 字符串。第 $i$ 行第 $j$ 个字符表示 $h_{i,j}$。

输出一行一个非负整数表示答案对 $998244353$ 取模后的结果。保证取模前答案不为 $0$。

**【样例 #1 解释】** 矩阵 $c$ 共有两种可能。 - 若 $c_{1,2}=1$，则使 $h$ 成为唯一最优解的 $(a,b)$ 共有 $12$ 种： - $a=[0,2]$，$b=[0,0]$； - $a=[0,2]$，$b=[0,1]$； - $a=[0,2]$，$b=[0,2]$； - $a=[0,2]$，$b=[1,0]$； - $a=[0,2]$，$b=[1,1]$； - $a=[0,2]$，$b=[1,2]$； - $a=[1,2]$，$b=[0,0]$； - $a=[1,2]$，$b=[0,1]$； - $a=[1,2]$，$b=[0,2]$； - $a=[1,2]$，$b=[1,0]$； - $a=[1,2]$，$b=[1,1]$； - $a=[1,2]$，$b=[1,2]$。 - 若 $c_{1,2}=2$，则使 $h$ 成为唯一最优解的 $(a,b)$ 共有 $4$ 种： - $a=[0,2]$，$b=[0,2]$； - $a=[0,2]$，$b=[1,2]$； - $a=[1,2]$，$b=[0,2]$； - $a=[1,2]$，$b=[1,2]$。 因此，满足条件的数据共有 $12+4=16$ 份。 **【数据范围】** 对于所有测试数据，均有： - $1\le n,m\le 10$； - 对于所有 $1\le i\le n$，$1\le j\le n$，均有 $S_{i,j}\subseteq\{0,1,2\}$ 且 $S_{i,j}\neq\varnothing$。 - 对于所有 $1\le i\le n$，$1\le j\le n$，均有 $h_{i,j}\in\{0,1\}$。