F - Prefix Median Editorial /

Time Limit: 2 sec / Memory Limit: 256 MiB

配点 : 20002000

問題文

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

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

  • b1=(a1)b_1 = (a_1) の中央値
  • b2=(a1,a2,a3)b_2 = (a_1, a_2, a_3) の中央値
  • b3=(a1,a2,a3,a4,a5)b_3 = (a_1,a_2,a_3,a_4,a_5) の中央値
  • ::
  • bN=(a1,a2,a3,...,a2N1)b_N = (a_1,a_2,a_3, ..., a_{2N-1}) の中央値

bb としてありうる数列の数を modulo 109+710^{9} + 7 で求めてください。

制約

  • 1N501 ≦ N ≦ 50
  • 1ai2N11 ≦ a_i ≦ 2N-1
  • aia_i は整数

入力

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

NN
a1a_1 a2a_2 ...... a2N1a_{2N-1}

出力

答えを出力せよ。


入力例 1Copy

Copy
2
1 3 2

出力例 1Copy

Copy
3

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


入力例 2Copy

Copy
4
1 3 2 3 2 4 3

出力例 2Copy

Copy
16

入力例 3Copy

Copy
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

出力例 3Copy

Copy
911828634

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

Score : 20002000 points

Problem Statement

Snuke received an integer sequence aa of length 2N12N-1.

He arbitrarily permuted the elements in aa, then used it to construct a new integer sequence bb of length NN, as follows:

  • b1=b_1 = the median of (a1)(a_1)
  • b2=b_2 = the median of (a1,a2,a3)(a_1, a_2, a_3)
  • b3=b_3 = the median of (a1,a2,a3,a4,a5)(a_1, a_2, a_3, a_4, a_5)
  • ::
  • bN=b_N = the median of (a1,a2,a3,...,a2N1)(a_1, a_2, a_3, ..., a_{2N-1})

How many different sequences can be obtained as bb? Find the count modulo 109+710^{9} + 7.

Constraints

  • 1N501 ≤ N ≤ 50
  • 1ai2N11 ≤ a_i ≤ 2N-1
  • aia_i are integers.

Input

Input is given from Standard Input in the following format:

NN
a1a_1 a2a_2 ...... a2N1a_{2N-1}

Output

Print the answer.


Sample Input 1Copy

Copy
2
1 3 2

Sample Output 1Copy

Copy
3

There are three sequences that can be obtained as bb: (1,2)(1,2), (2,2)(2,2) and (3,2)(3,2). Each of these can be constructed from (1,2,3)(1,2,3), (2,1,3)(2,1,3) and (3,1,2)(3,1,2), respectively.


Sample Input 2Copy

Copy
4
1 3 2 3 2 4 3

Sample Output 2Copy

Copy
16

Sample Input 3Copy

Copy
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

Sample Output 3Copy

Copy
911828634

Print the count modulo 109+710^{9} + 7.



2025-06-24 (Tue)
07:32:14 +00:00