CF715E.Complete the Permutations

ZS the Coder is given two permutations p and q of {1, 2, ..., n}, but some of their elements are replaced with 0. The distance between two permutations p and q is defined as the minimum number of moves required to turn p into q. A move consists of swapping exactly 2 elements of p.

ZS the Coder wants to determine the number of ways to replace the zeros with positive integers from the set {1, 2, ..., n} such that p and q are permutations of {1, 2, ..., n} and the distance between p and q is exactly k.

ZS the Coder wants to find the answer for all 0 ≤ k ≤ n - 1. Can you help him?

ZS 这位程序员得到了两个 {1, 2, ..., n} 的排列 p 和 q，但其中部分元素被替换成了 0。排列 p 与 q 之间的距离定义为将 p 变为 q 所需的最少操作次数；每次操作恰好交换 p 中的两个元素。

ZS 这位程序员希望计算：将所有 0 替换为集合 {1, 2, ..., n} 中的正整数，使得 p 和 q 均为 {1, 2, ..., n} 的排列，且 p 与 q 之间的距离恰好为 k 的方案数。

ZS 这位程序员希望对所有满足 0 ≤ k ≤ n − 1 的 k 求出对应答案。你能帮他解决这个问题吗？

The first line of the input contains a single integer n (1 ≤ n ≤ 250) — the number of elements in the permutations.

The second line contains n integers, _p_1, _p_2, ..., p__n (0 ≤ p__i ≤ n) — the permutation p. It is guaranteed that there is at least one way to replace zeros such that p is a permutation of {1, 2, ..., n}.

The third line contains n integers, _q_1, _q_2, ..., q__n (0 ≤ q__i ≤ n) — the permutation q. It is guaranteed that there is at least one way to replace zeros such that q is a permutation of {1, 2, ..., n}.

输入的第一行包含一个整数 $n$（$1 \leq n \leq 250$）—— 表示排列中元素的个数。

第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$（$0 \leq p_i \leq n$）—— 表示排列 $p$。保证至少存在一种将零替换为适当数值的方式，使得 $p$ 成为集合 $\{1, 2, \dots, n\}$ 的一个排列。

第三行包含 $n$ 个整数 $q_1, q_2, \dots, q_n$（$0 \leq q_i \leq n$）—— 表示排列 $q$。保证至少存在一种将零替换为适当数值的方式，使得 $q$ 成为集合 $\{1, 2, \dots, n\}$ 的一个排列。

Print n integers, i-th of them should denote the answer for k = i - 1. Since the answer may be quite large, and ZS the Coder loves weird primes, print them modulo 998244353 = 223·7·17 + 1, which is a prime.

输出 $ n $ 个整数，其中第 $ i $ 个整数表示 $ k = i - 1 $ 时的答案。由于答案可能非常大，而 ZS the Coder 喜欢特殊的质数，因此请将结果对 $ 998244353 = 2^{23} \cdot 7 \cdot 17 + 1 $（该数是一个质数）取模后输出。

In the first sample case, there is the only way to replace zeros so that it takes 0 swaps to convert p into q, namely p = (1, 2, 3), q = (1, 2, 3).

There are two ways to replace zeros so that it takes 1 swap to turn p into q. One of these ways is p = (1, 2, 3), q = (3, 2, 1), then swapping 1 and 3 from p transform it into q. The other way is p = (1, 3, 2), q = (1, 2, 3). Swapping 2 and 3 works in this case.

Finally, there is one way to replace zeros so that it takes 2 swaps to turn p into q, namely p = (1, 3, 2), q = (3, 2, 1). Then, we can transform p into q like following: .

在第一个样例中，仅有一种方式将零替换为数字，使得将 $p$ 变换为 $q$ 所需的交换次数为 0，即 $p = (1, 2, 3),\ q = (1, 2, 3)$。

有且仅有两种方式将零替换为数字，使得将 $p$ 变换为 $q$ 所需的交换次数为 1。其中一种方式是 $p = (1, 2, 3),\ q = (3, 2, 1)$，此时对 $p$ 中的 1 和 3 进行一次交换即可得到 $q$；另一种方式是 $p = (1, 3, 2),\ q = (1, 2, 3)$，此时对 $p$ 中的 2 和 3 进行一次交换即可。

最后，仅有一种方式将零替换为数字，使得将 $p$ 变换为 $q$ 所需的交换次数为 2，即 $p = (1, 3, 2),\ q = (3, 2, 1)$。此时可按如下步骤将 $p$ 变换为 $q$：