ZS 编码器被给予 {1, 2, ..., n} 的两个排列 p 和 q,但其中一些元素被替换为 0。两个排列 p 和 q 之间的距离定义为将 p 变成 q 所需的最小移动次数。一次移动就是交换 p 的 2 个元素。
ZS 编码器想要确定用集合 {1, 2, ..., n} 中的正整数替换零的方法数量,使得 p 和 q 是 {1, 2, ..., n} 的排列,并且 p 和 q 之间的距离恰好为 k。
编码员 ZS 想要找到所有 0 ≤ k ≤ n - 1 的答案。你能帮助他吗?
输入
输入的第一行包含一个整数 n (1 ≤ n ≤ 250) — 排列中的元素数量。
第二行包含 n 个整数,p1, p2, ..., pn (0 ≤ pi ≤ n) - 排列 p。保证至少有一种方法来替换零,使得 p 是 {1, 2, ..., n} 的排列。
第三行包含 n 个整数 q1, q2, ..., qn (0 ≤ qi ≤ n) - 排列 q。保证至少有一种方法来替换零,使得 q 是 {1, 2, ..., n} 的排列。
输出
打印 n 个整数,其中第 i 个应该表示 k = i - 1 的答案。由于答案可能很大,而且编码员 ZS 喜欢奇怪的素数,所以打印它们对 998244353 = 223·7·17 + 1 取模,这是一个素数。
示例
输入 #1
3 1 0 0 0 2 0
输出 #1
1 2 1
输入 #2
4 1 0 0 3 0 0 0 4
输出 #2
0 2 6 4
输入 #3
6 1 3 2 5 4 6 6 4 5 1 0 0
输出 #3
0 0 0 0 1 1
输入#4
4 1 2 3 4 2 3 4 1
输出#4
0 0 0 1
注意
在第一个示例案例中,只有一种方法可以替换零,从而需要 0 次交换才能将 p 转换为 q,即 p = (1, 2, 3),q = (1, 2, 3)。
有两种方法可以替换零,以便需要 1 次交换才能将 p 变成 q。其中一种方法是 p = (1, 2, 3), q = (3, 2, 1),然后交换 p 中的 1 和 3 将其变换为 q。另一种方式是 p = (1, 3, 2),q = (1, 2, 3)。在这种情况下,交换 2 和 3 就可以了。
最后,有一种方法可以替换零,这样需要2次交换才能将p变成q,即p = (1, 3, 2),q = (3, 2, 1)。然后,我们可以将 p 转换为 q,如下所示:$$(1,3,2)\to(2,3,1)\to(3,2,1)$$。