Up and Down#6852
A permutation of the set of numbers \{1, \ldots, 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_1, \ldots, u_N]: u_i is a minimum positive number where a_i < a_{i+k} holds. If no such number exists, then u_i = N + 1 - i.
Down-sequence [d_1, \ldots, d_N]: d_i is a minimum positive number where a_i > a_{i+k} holds. If no such number exists, 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 are multiple permutations that share 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 regarding 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 \le 17). The following two lines contain 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 regarding given up-sequence and down-sequence.
Primer 1