Color Problem

• 时间限制：$3.0$ 秒
• 空间限制：$512\text{ Mib}$

题目描述

给定一个 $3\times n$ 的网格图。定义一种染色方案是合法的，当且仅当：

• 每列恰好有一格被染色。
• 相邻两列被染色的格子不同。

其中，每个格子 $(i,j)$ 都有一个参数 $s_{i,j}$：

• 若 $s_{i,j}=\texttt{0}$，则表示该格子必须不染色。
• 若 $s_{i,j}=\texttt 1$，则表示该格子必须染色。
• 若 $s_{i,j}=\texttt ?$，则表示该格子可以染色或不染色。

你需要求出所有合法的染色方案的最大非染色格的连通块面积大小的和。由于答案可能较大，你只需要求出答案对 $998,244,353$ 取模后的结果。

输入格式

本题包含多组测试数据。

输入的第一行包含两个非负整数 $c,t$，分别表示测试点编号与测试数据组数。$c=0$ 表示该测试点为样例。

接下来依次输入每组测试数据，对于每组测试数据：

• 第一行包含一个正整数 $n$。
• 接下来三行，第 $i$ 行包含一个长度为 $n$ 的字符串 $s_{i,1},\dots,s_{i,n}$。

输出格式

对于每组测试数据：

• 输出一行，包含一个非负整数，表示所有合法的染色方案的最大非染色格的连通块面积大小的和对 $998,244,353$ 取模的结果。

样例 1 输入

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

样例 1 输出

5
6
20

样例 1 解释

本组样例包含 $3$ 组测试数据。

• 对于第 $1$ 组测试数据：
  • 若 $(1,1)$ 被染色，则最大非染色格的连通块面积大小为 $2$。
  • 若 $(2,1)$ 被染色，则最大非染色格的连通块面积大小为 $1$。
  • 若 $(3,1)$ 被染色，则最大非染色格的连通块面积大小为 $2$。
  • 所有方案总和为 $(2 + 1 + 2) \bmod 998,244,353 = 5$。
• 对于第 $2$ 组测试数据：
  • 若 $(1,1)$ 被染色，则最大非染色格的连通块面积大小为 $3$。
  • 若 $(3,1)$ 被染色，则最大非染色格的连通块面积大小为 $3$。
  • 注意，$\boldsymbol{(2,1)}$ 被染色的情况不属于合法方案，因为一个染色方案是合法的需要满足相邻两列被染色的格子不同。
  • 所有方案总和为 $(3 + 3) \bmod 998,244,353 = 6$。

数据范围

对于所有测试数据，均有：

• $1 \le t \le 5$；
• $1 \le n \le 300$；
• 对于所有 $1 \le i \le 3$ 和 $1 \le j \le n$，$s_{i,j} \in \{\texttt 0,\texttt 1 ,\texttt ?\}$。

• 特殊性质 A：对于所有 $1 \le i \le 3$ 和 $1 \le j \le n$，保证 $s_{i,j} \ne \texttt ?$。
• 特殊性质 B：对于所有 $1 \le i \le n$，保证 $s_{1,i} = \texttt 0$。
• 特殊性质 C：对于所有 $1 \le i \le 3$ 和 $1 \le j \le n$，若 $(i+j) \bmod 2 = 0$，则有 $s_{i,j} = 0$。