409258: GYM103469 J Joke
Description
Consider two permutations of integers from $$$1$$$ to $$$n$$$: $$$p$$$ and $$$q$$$. Let us call a binary string $$$s$$$ of length $$$n$$$ satisfying if there exists a matrix $$$a$$$ with dimensions $$$2 \times n$$$ such that:
- Every integer from $$$1$$$ to $$$2n$$$ appears exactly once in the matrix.
- The elements in the first row are ordered correspondingly to permutation $$$p$$$. More formally, $$$a_{1, i} < a_{1, j} \iff p_i < p_j$$$ for $$$1 \le i < j \le n$$$.
- The elements in the second row are ordered correspondingly to permutation $$$q$$$. More formally, $$$a_{2, i} < a_{2, j} \iff q_i < q_j$$$ for $$$1 \le i < j \le n$$$.
- For every $$$i$$$ from $$$1$$$ to $$$n$$$, we have $$$a_{1, i} < a_{2, i} \iff s_i = \texttt{0}$$$.
For two permutations $$$p$$$ and $$$q$$$ of size $$$n$$$, let us define $$$f(p, q)$$$ as the number of satisfying strings $$$s$$$ for them.
You are given all elements of $$$p$$$, and several elements of $$$q$$$, but forgot others. Find the sum of $$$f(p, q)$$$ over all permutations $$$q$$$ with the given known elements, modulo $$$998\,244\,353$$$.
InputThe first line of the input contains a single integer $$$n$$$ ($$$1 \le n \le 100$$$).
The second line of the input contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$, all $$$p_i$$$ are distinct), a permutation of numbers from $$$1$$$ to $$$n$$$.
The second line of the input contains $$$n$$$ integers $$$q_1, q_2, \ldots, q_n$$$ ($$$0 \le q_i \le n$$$, $$$q_i \neq q_j$$$ when $$$q_i \neq 0$$$ and $$$q_j \neq 0$$$). If $$$q_i \neq 0$$$, the respective element is given. If $$$q_i = 0$$$, its value is forgotten. All given elements are distinct.
OutputOutput the sum of $$$f(p, q)$$$ over all valid permutations $$$q$$$ modulo $$$998\,244\,353$$$.
ExamplesInput2 1 2 2 1Output
3Input
4 4 3 2 1 4 3 2 1Output
16Input
5 1 2 3 4 5 0 0 0 0 0Output
1546Input
6 1 6 2 5 3 4 0 1 0 2 0 3Output
52