{"raw_statement":[{"iden":"problem statement","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$."},{"iden":"constraints","content":"*   $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$)"},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $A_2$ $...$ $A_{2N}$"},{"iden":"sample input 1","content":"3\n1 -1 -1 3 6 -1"},{"iden":"sample output 1","content":"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."},{"iden":"sample input 2","content":"4\n7 1 8 3 5 2 6 4"},{"iden":"sample output 2","content":"1"},{"iden":"sample input 3","content":"10\n7 -1 -1 -1 -1 -1 -1 6 14 12 13 -1 15 -1 -1 -1 -1 20 -1 -1"},{"iden":"sample output 3","content":"9540576"},{"iden":"sample input 4","content":"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"},{"iden":"sample output 4","content":"374984201"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}