分数: 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.