Problem Description

Given a $3 \times n$ grid. A coloring scheme is defined to be valid if and only if:

• In each column, exactly one cell is colored.
• The colored cells in two adjacent columns are different.

For each cell $(i,j)$, there is a parameter $s_{i,j}$:

• If $s_{i,j}=\texttt{0}$, it means this cell must not be colored.
• If $s_{i,j}=\texttt 1$, it means this cell must be colored.
• If $s_{i,j}=\texttt ?$, it means this cell may be colored or not colored.

You need to compute the sum, over all valid coloring schemes, of the maximum connected component area consisting of uncolored cells. Since the answer may be very large, output it modulo $998,244,353$.

Input Format

This problem contains multiple test cases.

The first line of input contains two non-negative integers $c,t$, representing the test point ID and the number of test cases, respectively. $c=0$ means this test point is the sample.

Then the test cases follow. For each test case:

• The first line contains a positive integer $n$.
• The next three lines: the $i$-th line contains a string of length $n$, $s_{i,1},\dots,s_{i,n}$.

Output Format

For each test case:

• Output one line containing a non-negative integer, which is the sum of the maximum connected component area of uncolored cells over all valid coloring schemes, modulo $998,244,353$.

0 3
1
?
?
?
2
?0
?1
?0
2
??
??
??

5
6
20

Hint

Sample 1 Explanation

This sample contains $3$ test cases.

• For test case $1$:
  • If $(1,1)$ is colored, then the maximum connected component area of uncolored cells is $2$.
  • If $(2,1)$ is colored, then the maximum connected component area of uncolored cells is $1$.
  • If $(3,1)$ is colored, then the maximum connected component area of uncolored cells is $2$.
  • The total over all schemes is $(2 + 1 + 2) \bmod 998,244,353 = 5$.
• For test case $2$:
  • If $(1,1)$ is colored, then the maximum connected component area of uncolored cells is $3$.
  • If $(3,1)$ is colored, then the maximum connected component area of uncolored cells is $3$.
  • Note that the case where $\boldsymbol{(2,1)}$ is colored is not a valid scheme, because a valid coloring scheme must satisfy that the colored cells in adjacent columns are different.
  • The total over all schemes is $(3 + 3) \bmod 998,244,353 = 6$.

Constraints

For all testdata:

• $1 \le t \le 5$;
• $1 \le n \le 300$;
• For all $1 \le i \le 3$ and $1 \le j \le n$, $s_{i,j} \in \{\texttt 0,\texttt 1 ,\texttt ?\}$.

::cute-table{tuack}

• Special Property A: For all $1 \le i \le 3$ and $1 \le j \le n$, it is guaranteed that $s_{i,j} \ne \texttt ?$.
• Special Property B: For all $1 \le i \le n$, it is guaranteed that $s_{1,i} = \texttt 0$.
• Special Property C: For all $1 \le i \le 3$ and $1 \le j \le n$, if $(i+j) \bmod 2 = 0$, then $s_{i,j} = 0$.

Translated by ChatGPT 5