Симетричний обхід

Церемонія відкриття Олімпійських ігор відбудеться на річці з командами на човнах. Розташування спортсменів на верхній частині човна було спроектовано у дуже специфічний спосіб: для кожної команди $n$ спортсменів (номерованих з $1$ до $n$) розміщені у вигляді бінарного дерева.

Організатор також спроектував прямий обхід, зворотний обхід і (можливо порожню) послідовну частину симетричного обходу бінарного дерева, якої повинна дотримуватись кожна команда.

Тепер, щоб переконатися, що існує достатньо розташувань дерев, щоб кожна команда могла мати унікальне, вам потрібно обчислити кількість різних можливих симетричних обходів, позначимо її $t$, за модулем простого числа $999999937$.

Вхідні дані

Складається з чотирьох рядків. Перший рядок містить число $n$. Кожний наступний рядок містить список з $n$ цілих чисел.

Другий рядок містить список $a_1,a_2,...,a_n$, де $a_k$ — це номер $k$-го спортсмена, який знаходиться у прямому обході.

Третій рядок містить список $b_1,b_2,...,b_n$, де $b_k$ — це номер $k$-го спортсмена, який знаходиться у зворотному обході.

Четвертий рядок містить список $c_1,c_2,...,c_n$, де $c_k$ — це номер $k$-го спортсмена, який знаходиться у симетричному обході, або $0$, якщо організатор не вказав, ким повинен бути цей $k$-й спортсмен.

Вихідні дані

Виведіть одне ціле число $s$: це єдине число таке, що $0\le s<999999937$ і для нього $t-s$ ділиться на $999999937$.

Приклади