题目描述

有一个长度为 $2N$ 的数列 $A_1,\ A_2,\ ...,\ A_{2N}$。每个 $A_i$ 要么等于 $-1$，要么是 $1$ 到 $2N$ 之间的整数。除了 $-1$ 以外，任意整数在 $A_i$ 中最多只出现一次。

すぬけ君会将所有 $A_i = -1$ 的位置，分别替换成 $1$ 到 $2N$ 的整数，使得最终的 $A_i$ 恰好是 $1,2,\ldots,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$ 取模。

输入格式

输入从标准输入读入，格式如下：

$N$ $A_1$ $A_2$ $\ldots$ $A_{2N}$

输出格式

输出所有可能的 $B_1,\ B_2,\ ...,\ B_N$ 的不同取值的个数，对 $10^9+7$ 取模。

样例 1

输入

3
1 -1 -1 3 6 -1

输出

5

样例 2

输入

4
7 1 8 3 5 2 6 4

输出

1

样例 3

输入

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

输出

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

输出

374984201

说明/提示

约束条件

• $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$）

样例解释 1

将 ${A_i}$ 补全为 $1,2,\ldots,2N$ 的排列的方法有 $6$ 种，对于每种情况，${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)$ 有 $5$ 种。

由 ChatGPT 4.1 翻译