Məsələlər
Vovochka
Vovochka
You are given an array of $3n$ integers $[a_1, a_2, \ldots, 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, \ldots, 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$.
\InputFile
The first line contains a single integer $n$ ($1 \le n \le 2000$).
The second line contains $3n$ integers $a_1, a_2, \ldots, a_{3n}$ ($1 \le a_i \le 3n$) --- elements of the array.
\OutputFile
Print a single integer --- the number of possible arrays $[b_1, b_2, \ldots, b_n]$, modulo $10^9 + 7$.
\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]$.
Giriş verilənləri #1
2 1 2 2 2 2 3
Çıxış verilənləri #1
1
Giriş verilənləri #2
2 1 2 3 1 2 3
Çıxış verilənləri #2
4
Giriş verilənləri #3
3 9 8 7 6 5 4 3 2 1
Çıxış verilənləri #3
21