当前没有测试数据。

问题重述

由 $3 \times n$ 个单元格构成的 $3$ 行 $n$ 列异形数独规则如下：

• 每个单元格需填入 $1$ 到 $9$ 之间的整数。
• 任意一个 $3 \times 3$ 的子矩阵中不能包含重复数字。

给定部分已填入的数字（用 ? 表示未填），需计算可构造的合法解数量。答案需对 $10^9+7$ 取模。

输入格式：

• 第一行输入整数 $T$（$1 \leq T \leq 100$），代表测试数据组数。
• 每组测试数据：
  • 第一行输入整数 $n$（$3 \leq n \leq 10^5$），代表列数。
  • 接下来三行，每行输入一个长度为 $n$ 的字符串，由 $1\sim9$ 的数字和 ? 组成，代表当前矩阵状态。
  • 单个测试文件所有 $n$ 之和不超过 $3 \times 10^5$。

输出格式：

• 每组测试数据输出一行整数，代表合法解数量对 $10^9+7$ 取模的结果。

示例说明

示例 1：

输入：
4
6
1???56
456789
7891??
3
???
???
?11
3
123
456
789
3
723
18?
?9?

输出：
2
0
1
6

解释：

• 第一组（$n=6$）：存在两种合法解，如矩阵：

  1 2 3 4 5 6
  4 5 6 7 8 9
  7 8 9 1 2 3
  

  或

  1 3 2 4 5 6
  4 5 6 7 8 9
  7 8 9 1 3 2
  

• 第二组（$n=3$）：初始矩阵存在重复数字 1，无解。
• 第三组（$n=3$）：已填完整，唯一解。
• 第四组（$n=3$）：存在六种合法填充方式。