Задан массив из 3n целых чисел [a1,a2,…,a3n].
Вовочка разделил все элементы этого массива на n троек, вычислил медиану для каждой тройки и поместил полученные числа в отсортированном порядке в массив [b1,b2,…,bn].
Например, массив [1,2,3,1,2,3] может быть разделен на тройки (1,2,2) и (1,3,3). В этом случае массивом медиан будет [2,3].
Другим вариантом разделения на тройки будет (1,2,3),(1,2,3), массив медиан имеет вид [2,2].
Сколько различных массивов может получить Вовочка? Поскольку это число может быть очень большим, выведите его по модулю 109+7.
As a reminder, the median of three numbers is defined as follows: let a≤b≤c be these three numbers in sorted order, then the median is the number b.
The first line contains a single integer n (1≤n≤2000).
The second line contains 3n integers a1,a2,…,a3n (1≤ai≤3n) — elements of the array.
Print a single integer — the number of possible arrays [b1,b2,…,bn], modulo 109+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].