Score : 1600 points
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.
Input is given from Standard Input in the following format:
N A_1 A_2 ... A_{2N}
Print the number of different sequences that B_1, B_2, ..., B_N can be, modulo 10^9 + 7.
3 1 -1 -1 3 6 -1
5
There are six ways to make {A_i} a permutation of 1, 2, ..., 2N; for each of them, {B_i} would be as follows:
Thus, there are five different sequences that B_1, B_2, B_3 can be.
4 7 1 8 3 5 2 6 4
1
10 7 -1 -1 -1 -1 -1 -1 6 14 12 13 -1 15 -1 -1 -1 -1 20 -1 -1
9540576
20 -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