Вгору і вниз
Перестановка множини чисел {1, ..., N} — це зміна порядку цих чисел, де кожне число з'являється лише один раз. Ми визначаємо висхідну послідовність та низхідну послідовність перестановки наступним чином.
Висхідна послідовність [u_1, ..., u_N]: u_i — це найменше додатне число k, для якого виконується a_i < a_{i+k}. Якщо такого числа немає, то u_i = N + 1 - i.
Низхідна послідовність [d_1, ..., d_N]: d_i — це найменше додатне число k, для якого виконується a_i > a_{i+k}. Якщо такого числа немає, то d_i = N + 1 - i.
Наприклад, для перестановки [1, 4, 3, 2, 6, 5] висхідна послідовність дорівнює [1, 3, 2, 1, 2, 1], а низхідна послідовність дорівнює [6, 1, 1, 3, 1, 1].
Загалом існує більше однієї перестановки, яка має однакові висхідну та низхідну послідовності. Для наведеного прикладу, дві інші перестановки [1, 5, 4, 2, 6, 3] та [1, 5, 3, 2, 6, 4] мають таку ж висхідну та низхідну послідовності.
Вам потрібно підрахувати кількість перестановок, що відповідають заданим висхідній та низхідній послідовностям.
Вхідні дані
Вхід містить серію наборів даних.
Кожен набір складається з трьох рядків. Перший рядок містить одне додатне ціле число N (N ≤ 17). Наступні два рядки містять по N цілих чисел кожен, де перший рядок позначає висхідну послідовність, а другий — низхідну послідовність. Ці числа розділені пробілом.
Вхід завершується рядком, що містить один нуль. Цей рядок не слід обробляти.
Вихідні дані
Для кожного набору виведіть рядок, що містить кількість можливих перестановок, які відповідають заданим висхідній та низхідній послідовностям.