Вверх и Вниз
Перестановка множества чисел {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 целых чисел, где первая строка обозначает восходящую последовательность, а вторая — нисходящую последовательность. Эти числа разделены пробелом.
Ввод завершается строкой, содержащей один ноль. Эту строку обрабатывать не следует.
Выходные данные
Для каждого набора выведите строку, содержащую количество возможных перестановок, соответствующих заданным восходящей и нисходящей последовательностям.