AT_agc030_f.[AGC030F] Permutation and Minimum

有一个长度为 $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 \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 翻译