Odd Inversion Triple Partitioning

You are given an integer n and an integer sequence S of length 3n. Each element of S is an integer from 0 to 3 (inclusive). First, you must replace every occurrence of 0 with an integer from the set \(\{1,2,3\}\) arbitrarily, in order to obtain a new sequence \(T = t_1,t_2,\dots,t_{3n}\).

Then, you must partition the set \(\{1,2,\dots,3n\}\) into \(n\) disjoint triples \(\{a_{i,1},a_{i,2},a_{i,3}\}\) such that for every \(1 \le i \le n\) the indices satisfy \[ 1 \le a_{i,1} < a_{i,2} < a_{i,3} \le 3n, \] all the \(3n\) indices chosen (over all triples) are distinct, and for every triple the values \[ \{ t_{a_{i,1}}, t_{a_{i,2}}, t_{a_{i,3}} \} \] form a permutation of \(\{1,2,3\}\) whose inversion number is odd.

A permutation \(p_1,p_2,p_3\) of \(\{1,2,3\}\) has an inversion for every pair \((i,j)\) with \(i p_j\). For example, among the 6 permutations, the following three have an odd inversion count:

• \((1,3,2)\) because there is 1 inversion: \(3>2\).
• \((2,1,3)\) because there is 1 inversion: \(2>1\).
• \((3,2,1)\) because there are 3 inversions: \(3>2,3>1,2>1\).

Two solutions are considered essentially different if either the resulting sequence \(T\) is different or there exists some \(a_{i,j}\) that differs. Compute the number of essentially different solutions modulo \(10^9+7\).

Note. In other words, you must first choose a valid way to replace zeros so that the final sequence \(T\) has exactly \(n\) occurrences each of 1, 2, 3, and then choose a partition of indices into \(n\) triples so that in each triple (when the positions are sorted in increasing order) the three values form one of the three valid permutations with an odd number of inversions.

inputFormat

The first line contains a single integer n (\(1 \le n\le 5\)). (Note: the constraints in this version are small.)

The second line contains \(3n\) space‐separated integers, representing the sequence S. Each integer is between 0 and 3 (inclusive).

outputFormat

Output a single integer, the number of essentially different solutions modulo \(10^9+7\).

sample

1
1 3 2

1