#3738. 「LNOI2022」题

题目描述

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

1. $\forall 1 \le i \le n$，$1 \le a_{i, 1} < a_{i, 2} < a_{i, 3} \le 3n$；
2. $\forall (i_1, j_1) \ne (i_2, j_2)$，$a_{i_1, j_1} \ne a_{i_2, j_2}$；
3. $\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$，接下来一行一个长度为 $3n$ 的字符串描述序列 $S$。

输出格式

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

---

样例

输入

5
1
123
1
100
1
000
2
321321
2
000001

输出

0
1
3
6
60

前三组测试数据中 $n = 1$，故 $\{ a_{1, 1}, a_{1, 2}, a_{1, 3} \} = \{ 1, 2, 3 \}$。

• 对于第一组测试数据，只能有 $T = 123$，而 $\{ 1, 2, 3 \}$ 的逆序对数为 $0$ 不合法，故不存在方案。
• 对于第二组测试数据，$T = 123$ 不合法，而 $T = 132$ 时 $\{ 1, 3, 2 \}$ 的逆序对数为 $1$ 合法，故存在一个方案。
• 对于第三组测试数据，取 $T = 132$，$T = 213$，$T = 321$ 可以得到三个合法方案。
• 对于第四组测试数据，$T = 321321$，有六种方案。
• 对于第五组测试数据，输出 $60$。

---

样例 2

见附加文件中 problem2.in 和 problem2.ans。

该组样例中五组数据的 $n$ 分别为 $3, 5, 8, 12, 17$。

---

样例 3

见附加文件中 problem3.in 和 problem3.ans。

该组样例满足特殊性质 A，五组数据的 $n$ 分别为 $2, 4, 7, 15, 19$。

---

数据范围

对于所有测试数据，$1 \le C \le 5$，$1 \le n \le 19$，字符串 $S$ 的长度为 $3n$ 且仅由 $0, 1, 2, 3$ 构成。

测试点编号	$n \le$	特殊性质
1		无
2
3
4	5	A
5	7	无
6	10
7	13	A
8	16	无
9	18
10	19

特殊性质 A：字符串 $S$ 由全 $0$ 的字符串构成。

---

提示：请注意程序的空间消耗。