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

Есеп F. Кестені толтыру

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

1 second

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

256 megabytes

Өлшемі $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 )