You are given an array of 3n integers [a1,a2,…,a3n].
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 [b1,b2,…,bn].
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 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].