Вовочка

Задан массив из $3n$ целых чисел $[a_1,a_2,\dots ,a_{3n}]$.

Вовочка разделил все элементы этого массива на $n$ троек, вычислил медиану для каждой тройки и поместил полученные числа в отсортированном порядке в массив $[b_1,b_2,\dots ,b_n]$.

Например, массив $[1,2,3,1,2,3]$ может быть разделен на тройки $(1,2,2)$ и $(1,3,3)$. В этом случае массивом медиан будет $[2,3]$.

Другим вариантом разделения на тройки будет $(1,2,3),(1,2,3)$, массив медиан имеет вид $[2,2]$.

Сколько различных массивов может получить Вовочка? Поскольку это число может быть очень большим, выведите его по модулю $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$.

Входные данные

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.

Выходные данные

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

Примеры

Примечание

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