P17412 [MX-X31-T6] "FAOI-R14" Data Generator (Enhanced Version)

This problem is an enhanced version of [P17410 [MX-X31-T6] "FAOI-R14" Data Generator](https://www.luogu.com.cn/problem/P17410). The only difference is the range of $n, m$.

Little A created a problem for the Mengxiong Weekly Contest: > Given two integer sequences $a_1, a_2, \ldots, a_n$ and $b_1, b_2, \ldots, b_m$, and an $n \times m$ matrix $c$ whose elements all belong to $\{0,1,2\}$. > > For every $2$ in $c$, you need to replace it with $0$ or $1$; the original $0$ and $1$ in the matrix remain unchanged. After replacement, you obtain a $01$ matrix $d$. The matrix $d$ must satisfy: > - For all $i \in [1,n]$, $\sum_{j=1}^m d_{i,j} \ge a_i$; > - For all $j \in [1,m]$, $\sum_{i=1}^n d_{i,j} \ge b_j$; > > Among all matrices $d$ that satisfy the conditions above, you need to minimize the number of $1$ in the matrix. If a matrix $d$ satisfies the conditions above, and there does not exist another matrix that also satisfies the conditions above and has no more $1$ than it, then $d$ is called the unique optimal solution of the original problem. Little A is a "cold-hearted" problem setter and loves to handcraft testdata. Little A first chooses positive integers $n, m$, and an $n \times m$ set matrix $S$. For all $i \in [1,n]$ and $j \in [1,m]$, we have $S_{i,j} \subseteq \{0,1,2\}$ and $S_{i,j} \ne \varnothing$. Then, Little A independently generates one piece of data $(a,b,c)$ in the following way: - For all $i \in [1,n]$, choose $a_i$ uniformly at random from the integer set $\{0,1,\ldots,m\}$. - For all $j \in [1,m]$, choose $b_j$ uniformly at random from the integer set $\{0,1,\ldots,n\}$. - For all $i \in [1,n]$, $j \in [1,m]$, choose $c_{i,j}$ uniformly at random from the set $S_{i,j}$. Therefore, in total there can be $(m+1)^n (n+1)^m \prod_{i=1}^{n} \prod_{j=1}^{m} |S_{i,j}|$ different pieces of data. Obviously, the original problem may have multiple optimal solutions. As a "cold-hearted" problem setter, Little A naturally does not want to write an SPJ. However, considering that if a Mengxiong Weekly Contest problem goes wrong he will get his salary deducted, Little A still wants to know the probability that the judging can work correctly without an SPJ. Little A gives you his $n, m$, the set matrix $S$, and a fixed $n \times m$ $01$ matrix $h$. You need to compute, among all possible data $(a,b,c)$, how many pieces of data make $h$ the unique optimal solution of the original problem. Output the answer modulo $998244353$.

The first line contains two positive integers $n, m$, representing the matrix size. The next $n$ lines each contain a string of length $m$. Let the decimal integer represented by the $j$-th character in the $i$-th line be $x$, where $1 \le x \le 7$. For each $y \in \{0,1,2\}$, $y \in S_{i,j}$ if and only if the $y$-th bit (from low to high) in the binary representation of $x$ is $1$. The next $n$ lines describe the matrix $h$. Each line contains a `01` string of length $m$. The $j$-th character in the $i$-th line represents $h_{i,j}$.

Output one line containing a non-negative integer, representing the result modulo $998244353$. It is guaranteed that the answer before taking modulo is not $0$.

**Sample #1 Explanation** There are two possible matrices $c$. - If $c_{1,2} = 1$, then there are $12$ choices of $(a,b)$ that make $h$ the unique optimal solution: - $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]$. - If $c_{1,2} = 2$, then there are $4$ choices of $(a,b)$ that make $h$ the unique optimal solution: - $a=[0,2]$, $b=[0,2]$; - $a=[0,2]$, $b=[1,2]$; - $a=[1,2]$, $b=[0,2]$; - $a=[1,2]$, $b=[1,2]$. Therefore, there are $12+4=16$ pieces of data that satisfy the condition. **Constraints** For all testdata: - $1 \le n, m \le 10$; - For all $1 \le i \le n$, $1 \le j \le n$, $S_{i,j} \subseteq \{0,1,2\}$ and $S_{i,j} \ne \varnothing$. - For all $1 \le i \le n$, $1 \le j \le n$, $h_{i,j} \in \{0,1\}$. Translated by ChatGPT 5