P8366 [LNOI2022] Problem

You are given an integer sequence $S = s_1 s_2 \cdots s_{3 n}$ of length $3 n$, with values in $[0, 3]$. You first need to replace every $0$ in $S$ with any integer in $[1, 3]$, obtaining a sequence $T = t_1 t_2 \cdots t_{3 n}$. Then you need to provide $n$ integer sequences of length $3$, ${\{ a_{i, 1}, a_{i, 2}, a_{i, 3} \}}_{1 \le i \le n}$, such that: - $\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}} \}$ is a permutation of $\{ 1, 2, 3 \}$, and the number of inversions is odd. Two solutions are considered essentially different if and only if the sequence $T$ is different, or there exists some $a_{i, j}$ ($1 \le i \le n$, $1 \le j \le 3$) that is different. Find the number of essentially different solutions to the above operations, modulo $({10}^9 + 7)$.

**This problem has multiple test cases**. The first line of the input contains a positive integer $C$ indicating the number of test cases. For each test case, the first line contains an integer $n$. The next line contains a string of length $3 n$ describing the sequence $S$.

For each test case, output one line containing one integer: the number of solutions modulo $({10}^9 + 7)$.

**[Sample Explanation \#1]** In the first three test cases, $n = 1$, so $\{ a_{1, 1}, a_{1, 2}, a_{1, 3} \} = \{ 1, 2, 3 \}$. For the first test case, the only possible $T$ is $123$, and the number of inversions of $\{ 1, 2, 3 \}$ is $0$, which is invalid, so there is no solution. For the second test case, $T = 123$ is invalid, while for $T = 132$, the number of inversions of $\{ 1, 3, 2 \}$ is $1$, which is valid, so there is one solution. For the third test case, choosing $T = 132$, $T = 213$, or $T = 321$ gives three valid solutions. For the fourth test case, $T = 321321$, and there are six solutions as follows: - $\{ a_{1, 1}, a_{1, 2}, a_{1, 3} \} = \{ 1, 2, 3 \}$, $\{ a_{2, 1}, a_{2, 2}, a_{2, 3} \} = \{ 4, 5, 6 \}$ - $\{ a_{1, 1}, a_{1, 2}, a_{1, 3} \} = \{ 4, 5, 6 \}$, $\{ a_{2, 1}, a_{2, 2}, a_{2, 3} \} = \{ 1, 2, 3 \}$ - $\{ a_{1, 1}, a_{1, 2}, a_{1, 3} \} = \{ 1, 2, 6 \}$, $\{ a_{2, 1}, a_{2, 2}, a_{2, 3} \} = \{ 3, 4, 5 \}$ - $\{ a_{1, 1}, a_{1, 2}, a_{_{i, 3}} \} = \{ 3, 4, 5 \}$, $\{ a_{2, 1}, a_{2, 2}, a_{2, 3} \} = \{ 1, 2, 6 \}$ - $\{ a_{1, 1}, a_{1, 2}, a_{1, 3} \} = \{ 1, 5, 6 \}$, $\{ a_{2, 1}, a_{2, 2}, a_{2, 3} \} = \{ 2, 3, 4 \}$ - $\{ a_{1, 1}, a_{1, 2}, a_{1, 3} \} = \{ 2, 3, 4 \}$, $\{ a_{2, 1}, a_{2, 2}, a_{2, 3} \} = \{ 1, 5, 6 \}$ **[Sample \#2]** See ` problem/problem2.in` and `problem/problem2.ans` in the attachment. In this sample, the $n$ of the five test cases are $3, 5, 8, 12, 17$, respectively. **[Sample \#3]** See `problem/problem3.in` and `problem/problem3.ans` in the contestant directory. This sample satisfies special property A, and the $n$ of the five test cases are $2, 4, 7, 15, 19$, respectively. **[Constraints]** For all testdata, $1 \le C \le 5$, $1 \le n \le 19$. The length of the string $S$ is $3 n$, and it consists only of $0, 1, 2, 3$. | Test Point ID | $n \le$ | Special Property | |:-:|:-:|:-:| | $1$ | $1$ | None | | $2$ | $2$ | None | | $3$ | $3$ | None | | $4$ | $5$ | A | | $5$ | $7$ | None | | $6$ | $10$ | None | | $7$ | $13$ | A | | $8$ | $16$ | None | | $9$ | $18$ | None | | $10$ | $19$ | None | Special property A: the string $S$ consists of all $0$. **[Hint]** Please pay attention to the program’s memory usage. Translated by ChatGPT 5