A6605 | 「LNOI2022」题

给定长度为 $3 n$、值域为 $[0, 3]$ 的整数序列 $S = s_1 s_2 \cdots s_{3 n}$。你需要首先将 $S$ 中的每个 $0$ 替换为 $[1, 3]$ 中的任意一个整数，得到序列 $T = t_1 t_2 \cdots t_{3 n}$，然后给出 $n$ 个长度为 $3$ 的整数序列 ${\{ a_{i, 1}, a_{i, 2}, a_{i, 3} \}}_{1 \le i \le n}$，使得

- $\forall 1 \le i \le n$，$1 \le a_{i, 1} < a_{i, 2} < a_{i, 3} \le 3 n$；
- $\forall (i_1, j_1) \ne (i_2, j_2)$，$a_{i_1, j_1} \ne a_{i_2, j_2}$；
- $\forall 1 \le i \le n$，$\{ t_{a_{i, 1}}, t_{a_{i, 2}}, t_{a_{i, 3}} \}$ 是 $\{ 1, 2, 3 \}$ 的一个排列且逆序对数为奇数。

认为两个方案本质不同当且仅当序列 $T$ 不同或存在 $a_{i, j}$（$1 \le i \le n$，$1 \le j \le 3$）不同，求以上操作的本质不同的方案数，对 $({10}^9 + 7)$ 取模。

**本题有多组测试数据**。输入的第一行包含一个正整数 $C$ 表示测试数据组数。

对于每组测试数据，第一行一个整数 $n$，接下来一行一个长度为 $3 n$ 的字符串描述序列 $S$。

对于每组测试数据输出一行一个整数表示方案数对 $({10}^9 + 7)$ 取模的结果。