A permutation of the set of numbers \textbf{\{1, ..., N\}} is a reordering of these numbers, where each number appears just once. We define the \textit{up-sequence} and the \textit{down-sequence} of a permutation as follows. \textbf{Up-sequence} \textbf{\[u_1, ..., u_N\]}: \textbf{u_i} is a minimum positive number \textbf{k} where \textbf{a_i} < \textbf{a_\{i+k\}} holds. If there is not such a number, then \textbf{u_i = N + 1 - i}. \textbf{Down-sequence} \textbf{\[d_1, ..., d_N\]}: \textbf{d_i} is a minimum positive number \textbf{k} where \textbf{a_i} > \textbf{a_\{i+k\}} holds. If there is not such a number, then \textbf{d_i = N + 1 - i}. For example, given the permutation \textbf{\[1, 4, 3, 2, 6, 5\]}, the up-sequence is \textbf{\[1, 3, 2, 1, 2, 1\]} and the down-sequence is \textbf{\[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 \textbf{\[1, 5, 4, 2, 6, 3\]} and \textbf{\[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. \InputFile The input contains a series of data sets. Each set consists of three lines. The first line contains one positive integer \textbf{N} (\textbf{N} ≤ \textbf{17}). The following two lines contain \textbf{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. \OutputFile For each set, print a line containing the number of possible permutations in regard to given up-sequence and down-sequence.