[AGC012F] Prefix Median
题意翻译
给定一个长度为 $2n-1$ 的序列 $a$,你可以随意排列 $a$ 中的元素，请求出有多少种不同的序列 $b$，满足
* $b$ 的长度为 $n$。
* $b_i=\{a_1\ldots a_{2i-1}\}$ 的中位数。
$n\leq 50$。
答案对 $10^9+7$ 取模。
题目描述
[problemUrl]: https://atcoder.jp/contests/agc012/tasks/agc012_f
すぬけくんは長さ $ 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} $
输出格式
答えを出力せよ。
输入输出样例
输入样例 #1
2
1 3 2输出样例 #1
3输入样例 #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说明
### 制約
- $ 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 $ で割ったあまりを求めてください。