得分 : $1600$ 分

问题陈述

给定一个长度为 $2N$ 的序列：$A_1, A_2, ..., A_{2N}$。
每个 $A_i$ 可能是 $-1$ 或一个在 $1$ 到 $2N$（包括 $2N$）之间的整数。任何除 $-1$ 以外的整数在 ${A_i}$ 中最多出现一次。

对于每个 $i$ 使得 $A_i = -1$，Snuke 将 $A_i$ 替换为一个在 $1$ 到 $2N$（包括 $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$ 或 $1 \leq A_i \leq 2N$。
• 如果 $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$ 取模。

3
1 -1 -1 3 6 -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$ 可以形成五个不同的序列。

4
7 1 8 3 5 2 6 4

1

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

9540576

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

374984201