← 返回题目列表

AtCoder · agc030_f

F. 排列和最小值

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

分数: 1600 点

问题陈述

有一个长度为 2N: A_1, A_2, ..., A_{2N}。 每个 A_i 是 -1 或之间的整数 1 和 2N (含)。除以下任意整数 -1 最多出现一次 {A_i}.

对于每个 i 这样 A_i = -1, Snuke 取代 A_i 之间的整数 1 和 2N (含),因此 {A_i} 将是以下排列 1, 2, ..., 2N。 然后,他找到一个长度的序列 N, B_1, B_2, ..., B_N,如 B_i = min(A_{2i-1}, A_{2i}).

找出不同序列的数量 B_1, B_2, ..., B_N 可以是,模 10^9 + 7.

约束

  • 1 \leq N \leq 300
  • A_i = -1 or 1 \leq A_i \leq 2N.
  • If A_i \neq -1, A_j \neq -1,那么 A_i \neq A_j. (i \neq j)

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 ... A_{2N}

输出

打印不同序列的数量 B_1, B_2, ..., B_N 可以是,模 10^9 + 7.


示例输入 1

3
1 -1 -1 3 6 -1

示例输出 1

5

有六种方法可以制作 {A_i} 的排列 1, 2, ..., 2N;对于他们每个人来说, {B_i} 如下:

  • (A_1, A_2, A_3, A_4, A_5, A_6) = (1, 2, 4, 3, 6, 5): (B_1, B_2, B_3) = (1, 3, 5)
  • (A_1, A_2, A_3, A_4, A_5, A_6) = (1, 2, 5, 3, 6, 4): (B_1, B_2, B_3) = (1, 3, 4)
  • (A_1, A_2, A_3, A_4, A_5, A_6) = (1, 4, 2, 3, 6, 5): (B_1, B_2, B_3) = (1, 2, 5)
  • (A_1, A_2, A_3, A_4, A_5, A_6) = (1, 4, 5, 3, 6, 2): (B_1, B_2, B_3) = (1, 3, 2)
  • (A_1, A_2, A_3, A_4, A_5, A_6) = (1, 5, 2, 3, 6, 4): (B_1, B_2, B_3) = (1, 2, 4)
  • (A_1, A_2, A_3, A_4, A_5, A_6) = (1, 5, 4, 3, 6, 2): (B_1, B_2, B_3) = (1, 3, 2)

因此,有五种不同的序列 B_1, B_2, B_3 可以。


示例输入 2

4
7 1 8 3 5 2 6 4

示例输出 2

1

示例输入 3

10
7 -1 -1 -1 -1 -1 -1 6 14 12 13 -1 15 -1 -1 -1 -1 20 -1 -1

示例输出 3

9540576

示例输入 4

20
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 6 -1 -1 -1 -1 -1 7 -1 -1 -1 -1 -1 -1 -1 -1 -1 34 -1 -1 -1 -1 31 -1 -1 -1 -1 -1 -1 -1 -1

示例输出 4

374984201