22778번 - Up and Down 다국어

문제

A permutation of the set of numbers {1, . . . , N} is a reordering of these numbers, where each number appears just once. We define the up-sequence and the down-sequence of a permutation as follows.

• Up-sequence [u₁, . . . , u_N]: u_i is a minimum positive number k where a_i < a_i+k holds. If there is not such a number, then u_i = N + 1 − i.
• Down-sequence [d₁, . . . , d_N]: d_i is a minimum positive number k where a_i > a_i+k holds. If there is not such a number, then d_i = N + 1 − i.

For example, given the permutation [1, 4, 3, 2, 6, 5], the up-sequence is [1, 3, 2, 1, 2, 1] and the down-sequence is [6, 1, 1, 3, 1, 1].

In general there is more than one permutation that shares up-sequence and down-sequence. For the example above, two other permutations [1, 5, 4, 2, 6, 3] and [1, 5, 3, 2, 6, 4] share the same up-sequence and down-sequence.

You are requested to count the number of permutations in regard to given up-sequence and down-sequence.

입력

The input contains a series of data sets.

Each set consists of three lines. The first line contains one positive integer N (N ≤ 17). The following two lines contain N integers each, where the former line denotes an up-sequence and the latter a down-sequence. These integers are separated by a space.

The input is terminated by a line containing a single zero. This line should not be processed.

출력

For each set, print a line containing the number of possible permutations in regard to given up-sequence and down-sequence.

제한

힌트