任意の整数 \(1\leq i\leq N\) に対して、\(\min(A_{2i+ 1}, A_{2i + 2}) = -1\) が成り立つとします。

小さい値から順番に \(A\) に当てはめます。

\(dp[i][j][k]\) を \(i\) まで入れて、を以下の条件を満たす数列の数とします。

• 値はもともと \(A\) に入ってなかった \(i\) 以下の値で、大きい方の値がもともと \(A\) に入っていて、 \(i\) より大きいものの個数がちょうど\(j\) 個

• 値は \(i\) 以下の値で、大きい方の値がもともと \(A\) に入っていなくて、\(i\) より大きいものの個数がちょうど \(k\) 個

どのように更新するかを考えます。

\(i\) がもともと \(A\) に入っているとき

\(i\) を小さい値にするとき、\(k\) が \(1\) 増えます。

\(i\) を大きい値にするとき、\(j\) が \(1\) 減ります。また、どの値にするかで \(j\) 通りあります。

\(i\) がもともと \(A\) に入っていないとき

\(i\) を小さい値にするとき、 大きい値をもともと \(A\) に入っている値にするなら、 \(j\) が \(1\) 増え、そうでないなら \(k\) が \(1\) 増えます。

\(i\) を大きい値にするとき、 \(k\) が \(1\) 減ります。

この考えをもとに、\(dp[2N][0][0]\) を求めます。 そして、その値に \(\min(A_{2i+ 1}, A_{2i + 2}) = -1\) を満たす \(i\) の個数の階乗をかけたものが答えです。

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++)


#include <atcoder/modint>
using mint = atcoder::modint1000000007;


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    cin >> N;
    vector<int> A(N * 2);
    rep(i, 0, N * 2){
        cin >> A[i];
        A[i]--;
    }
    int X = 0;
    vector<int> seen(N * 2);
    rep(i, 0, N){
        if (A[i * 2] > A[i * 2 + 1]) swap(A[i * 2], A[i * 2 + 1]);
        if (A[i * 2] != -2){
            seen[A[i * 2]] = 2;
            seen[A[i * 2 + 1]] = 2;
        }
        else if (A[i * 2 + 1] == -2){
            X++;
        }
        else{
            seen[A[i * 2 + 1]] = 1;
        }
    }
    vector dp(N + 1, vector<mint>(N + 1));
    dp[0][0] = 1;
    rep(i, 0, N * 2){
        if (seen[i] == 2) continue;
        vector n_dp(N + 1, vector<mint>(N + 1));
        if (seen[i] == 1){
            rep(j, 0, N + 1) rep(k, 0, N + 1){
                if (j) n_dp[j - 1][k] += dp[j][k] * j;
                if (k != N) n_dp[j][k + 1] += dp[j][k];
            }
        }
        else{
            rep(j, 0, N + 1) rep(k, 0, N + 1){
                if (j != N) n_dp[j + 1][k] += dp[j][k];
                if (k != N) n_dp[j][k + 1] += dp[j][k];
                if (k) n_dp[j][k - 1] += dp[j][k];
            }
        }
        swap(n_dp, dp);
    }
    rep(i, 0, X) dp[0][0] *= i + 1;
    cout << dp[0][0].val() << "\n";
}