Background

This problem is an enhanced version of P17410 [MX-X31-T6] "FAOI-R14" Data Generator. The only difference is the range of $n, m$.

Problem Description

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$.

Input Format

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 Format

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$.

2 2
46
44
01
11

16

3 3
124
224
412
011
110
101

135

4 5
44646
75547
64745
75445
01101
10000
10101
00110

4064

8 8
66677655
77554747
73366765
21773775
73766676
73777775
77475565
56751776
11100100
10001010
11101110
10001010
01100111
10010010
10010010
01100111

46434700

Hint

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