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?

Input

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, p1, p2, ..., pn (0 ≤ pi ≤ 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, q1, q2, ..., qn (0 ≤ qi ≤ 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}.

Output

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.

Examples

Input

3
1 0 0
0 2 0


Output

1 2 1 


Input

4
1 0 0 3
0 0 0 4


Output

0 2 6 4 


Input

6
1 3 2 5 4 6
6 4 5 1 0 0


Output

0 0 0 0 1 1 


Input

4
1 2 3 4
2 3 4 1


Output

0 0 0 1 

Note

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: <image>.
#include <bits/stdc++.h>
using namespace std;
int dg[2010], a[2010], b[2010], n, dp[2010][2010];
int va[2010], vb[2010], v[2010], vs[2010], f[2010], g[2010], h[2010];
int A, B, X, C, D, fac[2010], inv[2010];
int gmod(int x) { return x >= 998244353 ? x - 998244353 : x; }
void mul(int a[], int b[], int c[]) {
  for (int i = 0; i <= n; ++i) h[i] = 0;
  for (int i = 0; i <= n; ++i)
    for (int j = 0; i + j <= n; ++j)
      h[i + j] = (h[i + j] + 1ll * a[i] * b[j]) % 998244353;
  for (int i = 0; i <= n; ++i) c[i] = h[i];
}
int qpow(int a, int b) {
  int ans = 1;
  for (; b; b >>= 1, a = 1ll * a * a % 998244353)
    if (b & 1) ans = 1ll * ans * a % 998244353;
  return ans;
}
int main() {
  scanf("%d", &n);
  fac[0] = inv[0] = 1;
  for (int i = 1; i <= n; ++i) fac[i] = 1ll * fac[i - 1] * i % 998244353;
  inv[n] = qpow(fac[n], 998244353 - 2);
  for (int i = n - 1; i >= 1; --i)
    inv[i] = 1ll * inv[i + 1] * (i + 1) % 998244353;
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), a[i] ? va[a[i]] = i : 0;
  for (int i = 1; i <= n; ++i) scanf("%d", &b[i]), b[i] ? vb[b[i]] = i : 0;
  for (int i = 1; i <= n; ++i)
    if (a[i] && b[i]) dg[a[i]]++, dg[b[i]]++;
  int N = n, X = 0;
  for (int i = 1, j; i <= n; ++i)
    if (!vs[i] && dg[i] == 1) {
      if (va[i]) {
        int x = va[i];
        vs[i] = 1;
        while (x) {
          int y = b[x];
          vs[y] = 1, x = va[y];
        }
      } else {
        int x = vb[i];
        vs[i] = 1;
        while (x) {
          int y = a[x];
          vs[y] = 1, x = vb[y];
        }
      }
    }
  for (int i = 1, j; i <= n; ++i)
    if (!vs[i] && dg[i] == 2) {
      for (j = i; !vs[j];) {
        int nxt = b[va[j]];
        vs[j] = 1, j = nxt;
      }
      X++;
    }
  for (int i = 1; i <= n; ++i)
    if (va[i] && vb[i]) N--;
  for (int i = 1; i <= n; ++i)
    if (((!!va[i]) ^ (!!vb[i]))) {
      if (va[i]) {
        int x = va[i];
        while (1) {
          int y = b[x];
          if (!y) {
            A++;
            break;
          }
          if (!va[y]) {
            C++;
            break;
          }
          x = va[y];
        }
      } else {
        int x = vb[i];
        while (1) {
          int y = a[x];
          if (!y) {
            B++;
            break;
          }
          if (!vb[y]) {
            C++;
            break;
          }
          x = vb[y];
        }
      }
    }
  C /= 2;
  D = N - A - B - C;
  g[X] = 1;
  memset(dp, 0, sizeof(dp));
  dp[0][0] = 1;
  for (int i = 1; i <= A; ++i)
    for (int j = 0; j <= i; ++j)
      dp[i][j] =
          ((j ? dp[i - 1][j - 1] : 0) + 1ll * dp[i - 1][j] * (A + D - i)) %
          998244353;
  mul(dp[A], g, g);
  memset(dp, 0, sizeof(dp));
  dp[0][0] = 1;
  for (int i = 1; i <= B; ++i)
    for (int j = 0; j <= i; ++j)
      dp[i][j] =
          ((j ? dp[i - 1][j - 1] : 0) + 1ll * dp[i - 1][j] * (B + D - i)) %
          998244353;
  mul(dp[B], g, g);
  memset(dp, 0, sizeof(dp));
  dp[0][0] = 1;
  for (int i = 1; i <= C; ++i)
    for (int j = 0, x = D - i + 1; j <= i; ++j)
      dp[i][j] = ((j ? 1ll * dp[i - 1][j - 1] * x : 0) +
                  1ll * dp[i - 1][j] * x * (x - 1)) %
                 998244353;
  mul(dp[C], g, g);
  D -= C;
  memset(dp, 0, sizeof(dp));
  dp[0][0] = 1;
  for (int i = 1; i <= D; ++i)
    for (int j = 0; j <= i; ++j)
      dp[i][j] = ((j ? 1ll * dp[i - 1][j - 1] * i : 0) +
                  1ll * dp[i - 1][j] * (D - i) * i) %
                 998244353;
  mul(dp[D], g, g);
  for (int i = 1; i <= n; ++i) printf("%d ", g[n - i + 1]);
}
