题目描述

すぬけくんは長さ $2N-1$ の数列 $a$ をもらいました。

すぬけくんは $a$ を自由に並び替えたあと、$a$ を使って新しい数列 $b$ を作りました。$b$ は以下に示されるような長さ $N$ の数列です。

• $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$ としてありうる数列の数を modulo $10^{9}\ +\ 7$ で求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

答えを出力せよ。

题目大意

给定一个长度为 $2n-1$ 的序列 $a$,你可以随意排列 $a$ 中的元素，请求出有多少种不同的序列 $b$，满足

• $b$ 的长度为 $n$。

• $b_i=\{a_1\ldots a_{2i-1}\}$ 的中位数。

$n\leq 50$。

答案对 $10^9+7$ 取模。

2
1 3 2

3

4
1 3 2 3 2 4 3

16

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

911828634

提示

制約

• $1\ ≦\ N\ ≦\ 50$
• $1\ ≦\ a_i\ ≦\ 2N-1$
• $a_i$ は整数

Sample Explanation 1

$b$ としてありうる数列は $(1,2),(2,2),(3,2)$ の $3$ 通りです。これらはそれぞれ $(1,2,3),(2,1,3),(3,1,2)$ から作ることが可能です。

Sample Explanation 3

$10^{9}\ +\ 7$ で割ったあまりを求めてください。