{"problem":{"name":"Permutation and Minimum","description":{"content":"There is a sequence of length $2N$: $A_1, A_2, ..., A_{2N}$. Each $A_i$ is either $-1$ or an integer between $1$ and $2N$ (inclusive). Any integer other than $-1$ appears at most once in ${A_i}$. For ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc030_f"},"statements":[{"statement_type":"Markdown","content":"There is a sequence of length $2N$: $A_1, A_2, ..., A_{2N}$. Each $A_i$ is either $-1$ or an integer between $1$ and $2N$ (inclusive). Any integer other than $-1$ appears at most once in ${A_i}$.\nFor each $i$ such that $A_i = -1$, Snuke replaces $A_i$ with an integer between $1$ and $2N$ (inclusive), so that ${A_i}$ will be a permutation of $1, 2, ..., 2N$. Then, he finds a sequence of length $N$, $B_1, B_2, ..., B_N$, as $B_i = min(A_{2i-1}, A_{2i})$.\nFind the number of different sequences that $B_1, B_2, ..., B_N$ can be, modulo $10^9 + 7$.\n\n## Constraints\n\n*   $1 \\leq N \\leq 300$\n*   $A_i = -1$ or $1 \\leq A_i \\leq 2N$.\n*   If $A_i \\neq -1, A_j \\neq -1$, then $A_i \\neq A_j$. ($i \\neq j$)\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$A_1$ $A_2$ $...$ $A_{2N}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc030_f","tags":[],"sample_group":[["3\n1 -1 -1 3 6 -1","5\n\nThere are six ways to make ${A_i}$ a permutation of $1, 2, ..., 2N$; for each of them, ${B_i}$ would be as follows:\n\n*   $(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)$\n*   $(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)$\n*   $(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)$\n*   $(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)$\n*   $(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)$\n*   $(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)$\n\nThus, there are five different sequences that $B_1, B_2, B_3$ can be."],["4\n7 1 8 3 5 2 6 4","1"],["10\n7 -1 -1 -1 -1 -1 -1 6 14 12 13 -1 15 -1 -1 -1 -1 20 -1 -1","9540576"],["20\n-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"]],"created_at":"2026-03-03 11:01:14"}}