Vovochka#10826
You are given an array of integers [a_1, a_2, \ldots, a_{3n}].
Vovochka divided all the elements of this array into 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 .
Another way to split into triples is (1, 2, 3), (1, 2, 3), then the array of medians would be .
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 .
The first line contains a single integer (1 \le n \le 2000).
The second line contains integers a_1, a_2, \ldots, 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, \ldots, b_n], modulo 10^9 + 7.
Example 1
Example 2
Example 3
In the first example, will always be equal to .
In the second example, arrays are possible: [1, 2], [1, 3], [2, 2], [2, 3].