Given an integer sequence $S = s_1 s_2 \cdots s_{3 n}$ of length $3 n$ with values in $[0, 3]$. You must first replace each $0$ in $S$ with any integer from $[1, 3]$ to obtain a sequence $T = t_1 t_2 \cdots t_{3 n}$, and then provide $n$ integer sequences of length $3$, denoted by $\{ 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 \}$ with an odd number of inversions.

Two schemes are considered distinct 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. Calculate the number of distinct schemes modulo $(10^9 + 7)$.

Input

This problem contains multiple test cases.

The first line contains a positive integer $C$ representing the number of test cases.

For each test case, the first line contains an integer $n$, and the next line contains a string of length $3 n$ describing the sequence $S$.

Output

For each test case, output a single integer representing the number of schemes modulo $(10^9 + 7)$.

Examples

Input 1

5
1
123
1
100
1
000
2
321321
2
000001

Output 1

0
1
3
6
60

Note 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, only $T = 123$ is possible, but the number of inversions of $\{ 1, 2, 3 \}$ is $0$, which is not odd, so no scheme exists.

For the second test case, $T = 123$ is invalid, while for $T = 132$, the set $\{ 1, 3, 2 \}$ has $1$ inversion, which is valid, so one scheme exists.

For the third test case, choosing $T = 132$, $T = 213$, or $T = 321$ yields three valid schemes.

For the fourth test case, with $T = 321321$, there are six valid schemes:

• $\{ 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_{1, 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 \}$

Examples 2

See the provided files.

In this set of examples, the values of $n$ for the five test cases are $3, 5, 8, 12, 17$ respectively.

Examples 3

See the provided files.

This set of examples satisfies special property A, and the values of $n$ for the five test cases are $2, 4, 7, 15, 19$ respectively.

Subtasks

For all test cases, $1 \le C \le 5$, $1 \le n \le 19$, and the string $S$ has length $3 n$ consisting only of $0, 1, 2, 3$.

Special Property A: The string $S$ consists entirely of $0$s.

Note

Please pay attention to the memory consumption of your program.