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