Problem Description

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)$.

Input Format

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$.

Output Format

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

5
1
123
1
100
1
000
2
321321
2
000001

0
1
3
6
60

Hint

[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$.

Special property A: the string $S$ consists of all $0$.

[Hint]

Please pay attention to the program’s memory usage.

Translated by ChatGPT 5