Vovochka

You are given an array of $3n$ integers $[a_1,a_2,\dots ,a_{3n}]$.

Vovochka divided all the elements of this array into $n$ triplets, calculated the median for each triple, and put the obtained numbers in the sorted order in the array $[b_1,b_2,\dots ,b_n]$.

For example, the array $[1,2,3,1,2,3]$ could be split into triplets $(1,2,2)$ and $(1,3,3)$. In this case, the median array would be $[2,3]$.

Another way to split into triples is $(1,2,3),(1,2,3)$, then the array of medians would be $[2,2]$.

How many distinct arrays could Vovochka get? Since this number can be very large, print it modulo $10^9+7$.

As a reminder, the median of three numbers is defined as follows: let $a\le b\le c$ be these three numbers in sorted order, then the median is the number $b$.

Input

The first line contains a single integer $n$ ($1\le n\le 2000$).

The second line contains $3n$ integers $a_1,a_2,\dots ,a_{3n}$ ($1\le a_i\le 3n$) — elements of the array.

Output

Print a single integer — the number of possible arrays $[b_1,b_2,\dots ,b_n]$, modulo $10^9+7$.

Examples

Note

In the first example, $b$ will always be equal to $[2,2]$.

In the second example, $4$ arrays $b$ are possible: $[1,2],[1,3],[2,2],[2,3]$.