AT_agc012_f [AGC012F] Prefix Median

题目描述

すぬけくん得到了一长度为 $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)$ 的中位数
• $\vdots$
• $b_N = (a_1, a_2, a_3, \ldots, a_{2N-1})$ 的中位数

请计算所有可能的 $b$ 数列的数目，对 $10^9+7$ 取模。

输入格式

输入通过标准输入给出，格式如下：

$N\ a_1\ a_2\ \dots\ a_{2N-1}$

输出格式

请输出答案。

样例 1

输入

2
1 3 2

输出

3

样例 2

输入

4
1 3 2 3 2 4 3

输出

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

输出

911828634

说明/提示

数据范围

• $1 \leq N \leq 50$
• $1 \leq a_i \leq 2N-1$
• $a_i$ 为整数

样例解释 1

所有可能的 $b$ 为 $(1, 2), (2, 2), (3, 2)$ 共 $3$ 种。这些分别可以由 $(1, 2, 3), (2, 1, 3), (3, 1, 2)$ 这三种排列构造得到。

样例解释 3

请输出对 $10^9+7$ 取模的结果。

由 ChatGPT 5 翻译