问题描述

有一个长度为 $2N$ 的序列：$A_1, A_2, ..., A_{2N}$。每个 $A_i$ 要么是 $-1$，要么是介于 $1$ 和 $2N$（包括）之间的整数。除了 $-1$ 之外的任何整数在 ${A_i}$ 中最多出现一次。

对于每个满足 $A_i = -1$ 的 $i$，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$ 或者 $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$ 取模。

示例输入 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