AT_agc030_f [AGC030F] Permutation and Minimum

[problemUrl]: https://atcoder.jp/contests/agc030/tasks/agc030_f 長さ $ 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

N/A

### 制約 - $ 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 $ 個あります．