题目描述

Snuke收到了一个长度为$2N-1$的整数序列$a$。

他任意排列了$a$中的元素，然后用它构建了一个新的长度为$N$的整数序列$b$，具体操作如下：

• $b_1 =$ $(a_1)$的中位数
• $b_2 =$ $(a_1, a_2, a_3)$的中位数
• $b_3 =$ $(a_1, a_2, a_3, a_4, a_5)$的中位数
• ...
• $b_N =$ $(a_1, a_2, a_3, ..., a_{2N-1})$的中位数

有多少个不同的序列可以作为$b$获得？将计数结果对$10^9+7$取模。

约束条件

• $1 ≤ N ≤ 50$
• $1 ≤ a_i ≤ 2N-1$
• $a_i$是整数。

输入

从标准输入读入输入数据，具体格式如下：

$N$ $a_1$ $a_2$ $...$ $a_{2N-1}$

输出

输出答案。

示例输入 1

2
1 3 2

示例输出 1

3

可以获得三个序列作为$b$：$(1,2)$，$(2,2)$和$(3,2)$。分别可以通过$(1,2,3)$，$(2,1,3)$和$(3,1,2)$构建。

示例输入 2

4
1 3 2 3 2 4 3

示例输出 2

16

示例输入 3

15
1 5 9 11 1 19 17 18 20 1 14 3 3 8 19 15 16 29 10 2 4 13 6 12 7 15 16 1 1

示例输出 3

911828634

将计数结果对$10^9+7$取模。