4-й этап Республиканской олимпиады по информатике 2022-2023, 2-й тур

Задача F. Заполнение таблицы

Ограничение по времени:

1 секунда

Ограничение по памяти:

256 мегабайт

Таблица размера $2 \times n$ называется красивой если числа в ней возрастают как по строкам, так и по столбцам, более того, все числа в таблице должны образовывать перестановку чисел от $1$ до $2 \cdot n$. Вам дана таблица в которой некоторые клетки заняты, а некоторые свободны. Вы уже умеете заполнять таблицу так, чтобы она стала красивой, и эта задача вам кажется скучной. Поэтому вы хотите узнать сколько есть способов заполнить таблицу таким образом, чтобы она была красивой. Так как ответ может быть очень большим, выведите его по модулю $10^9 + 7$.

Формат входного файла

В первой строке дано одно натуральное число $n$ ($1 <= n <= 2 \cdot 10^5$) — количество столбцов в таблице. Далее следуют $2$ строки, в этих двух строках вам дана сама таблица. Числа в таблице имеют значения от $0$ до $2 \cdot n$, при этом числа от $1$ до $2 \cdot n$ встречаются не более одного раза. Если значение элемента равно $0$, то это клетка считается пустой.

Формат выходного файла

Выведите одно число — ответ на задачу по модулю $10^9 + 7$.

Примеры:

Вход

3
5 0 6
4 0 0

Ответ

0

Вход

3
0 2 0
3 0 0

Ответ

2

Замечание

В первом примере нет ни единого способа заполнить таблицу так чтобы она была красивой. Во втором примере есть две красивые таблицы которые могут получиться:

( Altair Ashurov )