题目描述

長さ $2N$ の数列 $A_1,\ A_2,\ ...,\ A_{2N}$ があります． 各 $A_i$ は $-1$ か，あるいは $1$ 以上 $2N$ 以下の整数です． $-1$ 以外のどの整数も，${A_i}$ の中には $1$ 回までしか現れません．

すぬけ君は，$A_i\ =\ -1$ であるような $i$ それぞれに対して，$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$ で割ったあまりを求めてください．

输入格式

入力は以下の形式で標準入力から与えられる．

$N$ $A_1$ $A_2$ $...$ $A_{2N}$

输出格式

数列 $B_1,\ B_2,\ ...,\ B_N$ として考えられる異なるものの個数を $10^9\ +\ 7$ で割ったあまりを出力せよ．

题目大意

有一个 $2 N$ 个数的序列 $A$，从 $1$ 到 $2 N$ 标号。你要把 $1 \sim 2 N$ 这些数填进去，使它形成一个排列。

但是已经有一些位置强制填了特定的数了，输入时会给出。

最后令长度为 $N$ 的序列 $B$ 为：令 $B_i = \min\{A_{2 i - 1}, A_{2 i}\}$。

询问所有方案中能得到的不同的 $B$ 的数量。

• $1 \le N \le 300$。

3
1 -1 -1 3 6 -1

5

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

提示

制約

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

Sample Explanation 1

${A_i}$ を $1,\ 2,\ ...,\ 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$ 個あります．