Problem Statement

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 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})$.

Find the number of different sequences that $B_1, B_2, ..., B_N$ can be, modulo $10^9 + 7$.

Constraints

• $1 \leq N \leq 300$
• $A_i = -1$ or $1 \leq A_i \leq 2N$.
• If $A_i \neq -1, A_j \neq -1$, then $A_i \neq A_j$. ($i \neq j$)

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_{2N}

Output

Print the number of different sequences that $B_1, B_2, ..., B_N$ can be, modulo $10^9 + 7$.