← 返回题目列表

AtCoder · agc012_f

F. 前缀中位数

中文机器翻译题面 查看原题

分数: 2000 点

问题陈述

Snuke 收到一个整数序列 a 长度 2N-1.

他任意排列了其中的元素 a,然后用它构造一个新的整数序列 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?求计数模数 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.