Permutation Restoration

Unputdownable had a permutation \(a\) of length \(n\). For each index \(i\) (1-indexed) he defined:

\(l_i = \max\{ j < i \mid a_j < a_i \}\) with the convention that if no such \(j\) exists then \(l_i=0\);

\(r_i = \min\{ j > i \mid a_j < a_i \}\) with the convention that if no such \(j\) exists then \(r_i=n+1\).

After running his program to compute all \(l_i\) and \(r_i\), Unputdownable accidentally lost the original permutation \(a\). Moreover, the two arrays \(l=[l_1,\dots,l_n]\) and \(r=[r_1,\dots,r_n]\) were each independently reordered. That is, you are given the two multisets of numbers (one for the \(l\) values and one for the \(r\) values) that resulted from some original permutation \(a\).

Your task is to count how many original permutations \(a\) could have produced these two multisets. The answer should be given modulo \(998244353\).

Note on the definition: For a given permutation \(a\), the pair of values \((l_i, r_i)\) for each \(i\) is uniquely determined by the rule above. In a valid computed array (when the indices are in their original order) the following property holds: for any consecutive segment \([L,R]\) of indices, if you look for the index \(m\) in \([L,R]\) for which \(a_m\) is maximum, then necessarily \(l_m = L-1\) and \(r_m = R+1\). This hidden Cartesian‐tree structure is what “ties” the two arrays together. However, since the two arrays are given after an independent reordering, the original index–wise pairing is lost. It is guaranteed that the input data comes from at least one valid permutation.

Input constraints for this problem in our test data are small (\(n \le 8\)) so that a brute‐force solution is acceptable.

inputFormat

The first line contains a single integer \(n\) (\(1 \le n \le 8\)).

The second line contains \(n\) space‐separated integers representing the multiset of \(l_i\) values.

The third line contains \(n\) space‐separated integers representing the multiset of \(r_i\) values.

outputFormat

Output a single integer, which is the number of original permutations that could produce the given multisets, modulo \(998244353\).

sample

1
0
2

1