#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
void *wmem;
char memarr[209715200];
template <class S, class T>
inline S max_L(S a, T b) {
  return a >= b ? a : b;
}
template <class T>
inline void walloc1d(T **arr, int x, void **mem = &wmem) {
  static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
  (*mem) = (void *)(((char *)(*mem)) + skip[((unsigned long long)(*mem)) & 15]);
  (*arr) = (T *)(*mem);
  (*mem) = ((*arr) + x);
}
template <class T1>
void sortA_L(int N, T1 a[], void *mem = wmem) {
  sort(a, a + N);
}
template <class T1>
void rsortA_L(int N, T1 a[], void *mem = wmem) {
  sortA_L(N, a, mem);
  reverse(a, a + N);
}
struct Modint {
  unsigned val;
  Modint() { val = 0; }
  Modint(int a) { val = ord(a); }
  Modint(unsigned a) { val = ord(a); }
  Modint(long long a) { val = ord(a); }
  Modint(unsigned long long a) { val = ord(a); }
  inline unsigned ord(unsigned a) { return a % (998244353U); }
  inline unsigned ord(int a) {
    a %= (int)(998244353U);
    if (a < 0) {
      a += (998244353U);
    }
    return a;
  }
  inline unsigned ord(unsigned long long a) { return a % (998244353U); }
  inline unsigned ord(long long a) {
    a %= (int)(998244353U);
    if (a < 0) {
      a += (998244353U);
    }
    return a;
  }
  inline unsigned get() { return val; }
  inline Modint &operator+=(Modint a) {
    val += a.val;
    if (val >= (998244353U)) {
      val -= (998244353U);
    }
    return *this;
  }
  inline Modint &operator-=(Modint a) {
    if (val < a.val) {
      val = val + (998244353U) - a.val;
    } else {
      val -= a.val;
    }
    return *this;
  }
  inline Modint &operator*=(Modint a) {
    val = ((unsigned long long)val * a.val) % (998244353U);
    return *this;
  }
  inline Modint &operator/=(Modint a) { return *this *= a.inverse(); }
  inline Modint operator+(Modint a) { return Modint(*this) += a; }
  inline Modint operator-(Modint a) { return Modint(*this) -= a; }
  inline Modint operator*(Modint a) { return Modint(*this) *= a; }
  inline Modint operator/(Modint a) { return Modint(*this) /= a; }
  inline Modint operator+(int a) { return Modint(*this) += Modint(a); }
  inline Modint operator-(int a) { return Modint(*this) -= Modint(a); }
  inline Modint operator*(int a) { return Modint(*this) *= Modint(a); }
  inline Modint operator/(int a) { return Modint(*this) /= Modint(a); }
  inline Modint operator+(long long a) { return Modint(*this) += Modint(a); }
  inline Modint operator-(long long a) { return Modint(*this) -= Modint(a); }
  inline Modint operator*(long long a) { return Modint(*this) *= Modint(a); }
  inline Modint operator/(long long a) { return Modint(*this) /= Modint(a); }
  inline Modint operator-(void) {
    Modint res;
    if (val) {
      res.val = (998244353U) - val;
    } else {
      res.val = 0;
    }
    return res;
  }
  inline operator bool(void) { return val != 0; }
  inline operator int(void) { return get(); }
  inline operator long long(void) { return get(); }
  inline Modint inverse() {
    int a = val;
    int b = (998244353U);
    int u = 1;
    int v = 0;
    int t;
    Modint res;
    while (b) {
      t = a / b;
      a -= t * b;
      swap(a, b);
      u -= t * v;
      swap(u, v);
    }
    if (u < 0) {
      u += (998244353U);
    }
    res.val = u;
    return res;
  }
  inline Modint pw(unsigned long long b) {
    Modint a(*this);
    Modint res;
    res.val = 1;
    while (b) {
      if (b & 1) {
        res *= a;
      }
      b >>= 1;
      a *= a;
    }
    return res;
  }
  inline bool operator==(int a) { return ord(a) == val; }
  inline bool operator!=(int a) { return ord(a) != val; }
};
inline Modint operator+(int a, Modint b) { return Modint(a) += b; }
inline Modint operator-(int a, Modint b) { return Modint(a) -= b; }
inline Modint operator*(int a, Modint b) { return Modint(a) *= b; }
inline Modint operator/(int a, Modint b) { return Modint(a) /= b; }
inline Modint operator+(long long a, Modint b) { return Modint(a) += b; }
inline Modint operator-(long long a, Modint b) { return Modint(a) -= b; }
inline Modint operator*(long long a, Modint b) { return Modint(a) *= b; }
inline Modint operator/(long long a, Modint b) { return Modint(a) /= b; }
inline int my_getchar_unlocked() {
  static char buf[1048576];
  static int s = 1048576;
  static int e = 1048576;
  if (s == e && e == 1048576) {
    e = fread_unlocked(buf, 1, 1048576, stdin);
    s = 0;
  }
  if (s == e) {
    return EOF;
  }
  return buf[s++];
}
inline void rd(int &x) {
  int k;
  int m = 0;
  x = 0;
  for (;;) {
    k = my_getchar_unlocked();
    if (k == '-') {
      m = 1;
      break;
    }
    if ('0' <= k && k <= '9') {
      x = k - '0';
      break;
    }
  }
  for (;;) {
    k = my_getchar_unlocked();
    if (k < '0' || k > '9') {
      break;
    }
    x = x * 10 + k - '0';
  }
  if (m) {
    x = -x;
  }
}
struct MY_WRITER {
  char buf[1048576];
  int s;
  int e;
  MY_WRITER() {
    s = 0;
    e = 1048576;
  }
  ~MY_WRITER() {
    if (s) {
      fwrite_unlocked(buf, 1, s, stdout);
    }
  }
};
MY_WRITER MY_WRITER_VAR;
void my_putchar_unlocked(int a) {
  if (MY_WRITER_VAR.s == MY_WRITER_VAR.e) {
    fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
    MY_WRITER_VAR.s = 0;
  }
  MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
}
inline void wt_L(char a) { my_putchar_unlocked(a); }
inline void wt_L(int x) {
  int s = 0;
  int m = 0;
  char f[10];
  if (x < 0) {
    m = 1;
    x = -x;
  }
  while (x) {
    f[s++] = x % 10;
    x /= 10;
  }
  if (!s) {
    f[s++] = 0;
  }
  if (m) {
    my_putchar_unlocked('-');
  }
  while (s--) {
    my_putchar_unlocked(f[s] + '0');
  }
}
inline void wt_L(Modint x) {
  int i;
  i = (int)x;
  wt_L(i);
}
template <class S, class T>
inline S chmax(S &a, T b) {
  if (a < b) {
    a = b;
  }
  return a;
}
template <class T>
struct Comb {
  int mem_fact;
  T *factri;
  T *ifactri;
  Comb() { mem_fact = 0; }
  inline void expand_fact(int k) {
    if (k <= mem_fact) {
      return;
    }
    chmax(k, 2 * mem_fact);
    if (mem_fact == 0) {
      int i;
      factri = (T *)malloc(k * sizeof(T));
      ifactri = (T *)malloc(k * sizeof(T));
      factri[0] = 1;
      for (i = (1); i < (k); i++) {
        factri[i] = i * factri[i - 1];
      }
      ifactri[k - 1] = 1 / factri[k - 1];
      for (i = (k - 1) - 1; i >= (0); i--) {
        ifactri[i] = (i + 1) * ifactri[i + 1];
      }
    } else {
      int i;
      factri = (T *)realloc(factri, k * sizeof(T));
      ifactri = (T *)realloc(ifactri, k * sizeof(T));
      for (i = (mem_fact); i < (k); i++) {
        factri[i] = i * factri[i - 1];
      }
      ifactri[k - 1] = 1 / factri[k - 1];
      for (i = (k - 1) - 1; i >= (mem_fact); i--) {
        ifactri[i] = (i + 1) * ifactri[i + 1];
      }
    }
    mem_fact = k;
  }
  inline T fac(int k) {
    if (mem_fact < k + 1) {
      expand_fact(k + 1);
    }
    return factri[k];
  }
  inline T ifac(int k) {
    if (mem_fact < k + 1) {
      expand_fact(k + 1);
    }
    return ifactri[k];
  }
  inline T C(int a, int b) {
    if (b < 0 || b > a) {
      return 0;
    }
    if (mem_fact < a + 1) {
      expand_fact(a + 1);
    }
    return factri[a] * ifactri[b] * ifactri[a - b];
  }
  inline T P(int a, int b) {
    if (b < 0 || b > a) {
      return 0;
    }
    if (mem_fact < a + 1) {
      expand_fact(a + 1);
    }
    return factri[a] * ifactri[a - b];
  }
  inline T H(int a, int b) {
    if (a == 0 && b == 0) {
      return 1;
    }
    if (a <= 0 || b < 0) {
      return 0;
    }
    if (mem_fact < a + b) {
      expand_fact(a + b);
    }
    return C(a + b - 1, b);
  }
  inline T Multinomial(int sz, int a[]) {
    int i;
    int s = 0;
    T res;
    for (i = (0); i < (sz); i++) {
      s += a[i];
    }
    if (mem_fact < s + 1) {
      expand_fact(s + 1);
    }
    res = factri[s];
    for (i = (0); i < (sz); i++) {
      res *= ifactri[a[i]];
    }
    return 1;
  }
  inline T Multinomial(int a) { return 1; }
  inline T Multinomial(int a, int b) {
    if (mem_fact < a + b + 1) {
      expand_fact(a + b + 1);
    }
    return factri[a + b] * ifactri[a] * ifactri[b];
  }
  inline T Multinomial(int a, int b, int c) {
    if (mem_fact < a + b + c + 1) {
      expand_fact(a + b + c + 1);
    }
    return factri[a + b + c] * ifactri[a] * ifactri[b] * ifactri[c];
  }
  inline T Multinomial(int a, int b, int c, int d) {
    if (mem_fact < a + b + c + d + 1) {
      expand_fact(a + b + c + d + 1);
    }
    return factri[a + b + c + d] * ifactri[a] * ifactri[b] * ifactri[c] *
           ifactri[d];
  }
  inline T Catalan(int n) {
    if (n < 0) {
      return 0;
    }
    if (mem_fact < 2 * n + 1) {
      expand_fact(2 * n + 1);
    }
    return factri[2 * n] * ifactri[n] * ifactri[n + 1];
  }
  inline T C_s(long long a, long long b) {
    long long i;
    T res;
    if (b < 0 || b > a) {
      return 0;
    }
    if (b > a - b) {
      b = a - b;
    }
    res = 1;
    for (i = (0); i < (b); i++) {
      res *= a - i;
      res /= i + 1;
    }
    return res;
  }
  inline T P_s(long long a, long long b) {
    long long i;
    T res;
    if (b < 0 || b > a) {
      return 0;
    }
    res = 1;
    for (i = (0); i < (b); i++) {
      res *= a - i;
    }
    return res;
  }
  inline T per_s(long long n, long long k) {
    T d;
    int m;
    if (n < 0 || k < 0) {
      return 0;
    }
    if (n == k && k == 0) {
      return 1;
    }
    if (n == 0 || k == 0) {
      return 0;
    }
    if (k == 1) {
      return 1;
    }
    if (k == 2) {
      d = n / 2;
      return d;
    }
    if (k == 3) {
      d = (n - 1) / 6;
      m = (n - 1) % 6;
      if (m == 0) {
        return 3 * d * d + d;
      }
      if (m == 1) {
        return 3 * d * d + 2 * d;
      }
      if (m == 2) {
        return 3 * d * d + 3 * d + 1;
      }
      if (m == 3) {
        return 3 * d * d + 4 * d + 1;
      }
      if (m == 4) {
        return 3 * d * d + 5 * d + 2;
      }
      if (m == 5) {
        return 3 * d * d + 6 * d + 3;
      }
    }
    assert(0 && "per_s should be k <= 3");
    return -1;
  }
};
template <class T>
struct LHeap {
  int *hp;
  int *place;
  int size;
  T *val;
  void malloc(int N) {
    hp = (int *)std::malloc(N * sizeof(int));
    place = (int *)std::malloc(N * sizeof(int));
    val = (T *)std::malloc(N * sizeof(T));
  }
  void walloc(int N, void **mem = &wmem) {
    walloc1d(&hp, N, mem);
    walloc1d(&place, N, mem);
    walloc1d(&val, N, mem);
  }
  void free() {
    std::free(hp);
    std::free(place);
    std::free(val);
  }
  void init(int N) {
    int i;
    size = 0;
    for (i = (0); i < (N); i++) {
      place[i] = -1;
    }
  }
  void up(int n) {
    int m;
    while (n) {
      m = (n - 1) / 2;
      if (val[hp[m]] <= val[hp[n]]) {
        break;
      }
      swap(hp[m], hp[n]);
      swap(place[hp[m]], place[hp[n]]);
      n = m;
    }
  }
  void down(int n) {
    int m;
    for (;;) {
      m = 2 * n + 1;
      if (m >= size) {
        break;
      }
      if (m + 1 < size && val[hp[m]] > val[hp[m + 1]]) {
        m++;
      }
      if (val[hp[m]] >= val[hp[n]]) {
        break;
      }
      swap(hp[m], hp[n]);
      swap(place[hp[m]], place[hp[n]]);
      n = m;
    }
  }
  void change(int n, T v) {
    T f = val[n];
    val[n] = v;
    if (place[n] == -1) {
      place[n] = size;
      hp[size++] = n;
      up(place[n]);
    } else {
      if (f < v) {
        down(place[n]);
      } else if (f > v) {
        up(place[n]);
      }
    }
  }
  int pop(void) {
    int res = hp[0];
    place[res] = -1;
    size--;
    if (size) {
      hp[0] = hp[size];
      place[hp[0]] = 0;
      down(0);
    }
    return res;
  }
};
struct fft_pnt {
  double x;
  double y;
  fft_pnt(void) {}
  fft_pnt(double a, double b) {
    x = a;
    y = b;
  }
  void set(double a, double b) {
    x = a;
    y = b;
  }
  fft_pnt &operator+=(fft_pnt a) {
    x += a.x;
    y += a.y;
    return *this;
  }
  fft_pnt &operator-=(fft_pnt a) {
    x -= a.x;
    y -= a.y;
    return *this;
  }
  fft_pnt &operator*=(fft_pnt a) {
    fft_pnt p = *this;
    x = p.x * a.x - p.y * a.y;
    y = p.x * a.y + p.y * a.x;
    return *this;
  }
  fft_pnt operator+(fft_pnt a) { return fft_pnt(*this) += a; }
  fft_pnt operator-(fft_pnt a) { return fft_pnt(*this) -= a; }
  fft_pnt operator*(fft_pnt a) { return fft_pnt(*this) *= a; }
};
void fft_L(int n, fft_pnt x[], void *mem) {
  int i;
  int j;
  int n1;
  int n2;
  int n3;
  int step = 1;
  double theta = 2 * 3.14159265358979323846 / n;
  double tmp;
  fft_pnt w1;
  fft_pnt w2;
  fft_pnt w3;
  fft_pnt a;
  fft_pnt b;
  fft_pnt c;
  fft_pnt d;
  fft_pnt aa;
  fft_pnt bb;
  fft_pnt cc;
  fft_pnt dd;
  fft_pnt *y = (fft_pnt *)mem;
  while (n > 2) {
    n1 = n / 4;
    n2 = n1 + n1;
    n3 = n1 + n2;
    for (i = (0); i < (n1); i++) {
      w1 = fft_pnt(cos(i * theta), -sin(i * theta));
      w2 = w1 * w1;
      w3 = w1 * w2;
      for (j = (0); j < (step); j++) {
        a = x[j + step * i];
        b = x[j + step * (i + n1)];
        c = x[j + step * (i + n2)];
        d = x[j + step * (i + n3)];
        aa = a + c;
        bb = a - c;
        cc = b + d;
        dd = b - d;
        tmp = dd.y;
        dd.y = dd.x;
        dd.x = -tmp;
        y[j + step * (4 * i)] = aa + cc;
        y[j + step * (4 * i + 1)] = w1 * (bb - dd);
        y[j + step * (4 * i + 2)] = w2 * (aa - cc);
        y[j + step * (4 * i + 3)] = w3 * (bb + dd);
      }
    }
    n /= 4;
    step *= 4;
    theta *= 4;
    swap(x, y);
  }
  if (n == 2) {
    for (i = (0); i < (step); i++) {
      y[i] = x[i] + x[i + step];
      y[i + step] = x[i] - x[i + step];
    }
    n /= 2;
    step *= 2;
    theta *= 2;
    swap(x, y);
  }
  for (i = (0); i < (step); i++) {
    y[i] = x[i];
  }
}
void fftinv_L(int n, fft_pnt x[], void *mem) {
  int i;
  int j;
  int n1;
  int n2;
  int n3;
  int step = 1;
  double theta = 2 * 3.14159265358979323846 / n;
  double tmp;
  fft_pnt w1;
  fft_pnt w2;
  fft_pnt w3;
  fft_pnt a;
  fft_pnt b;
  fft_pnt c;
  fft_pnt d;
  fft_pnt aa;
  fft_pnt bb;
  fft_pnt cc;
  fft_pnt dd;
  fft_pnt *y = (fft_pnt *)mem;
  while (n > 2) {
    n1 = n / 4;
    n2 = n1 + n1;
    n3 = n1 + n2;
    for (i = (0); i < (n1); i++) {
      w1 = fft_pnt(cos(i * theta), sin(i * theta));
      w2 = w1 * w1;
      w3 = w1 * w2;
      for (j = (0); j < (step); j++) {
        a = x[j + step * i];
        b = x[j + step * (i + n1)];
        c = x[j + step * (i + n2)];
        d = x[j + step * (i + n3)];
        aa = a + c;
        bb = a - c;
        cc = b + d;
        dd = b - d;
        tmp = dd.y;
        dd.y = dd.x;
        dd.x = -tmp;
        y[j + step * (4 * i)] = aa + cc;
        y[j + step * (4 * i + 1)] = w1 * (bb + dd);
        y[j + step * (4 * i + 2)] = w2 * (aa - cc);
        y[j + step * (4 * i + 3)] = w3 * (bb - dd);
      }
    }
    n /= 4;
    step *= 4;
    theta *= 4;
    swap(x, y);
  }
  if (n == 2) {
    for (i = (0); i < (step); i++) {
      y[i] = x[i] + x[i + step];
      y[i + step] = x[i] - x[i + step];
    }
    n /= 2;
    step *= 2;
    theta *= 2;
    swap(x, y);
  }
  for (i = (0); i < (step); i++) {
    y[i] = x[i];
  }
}
void convolution_L(double A[], int As, double B[], int Bs, double res[], int Rs,
                   void *mem = wmem) {
  int i;
  int n;
  int n2;
  double mul;
  fft_pnt *a;
  fft_pnt *b;
  n = max_L(As + Bs, Rs);
  for (n2 = 1; n2 < n; n2 *= 2) {
    ;
  }
  walloc1d(&a, n2, &mem);
  walloc1d(&b, n2, &mem);
  for (i = (0); i < (As); i++) {
    a[i].set(A[i], 0);
  }
  int Nwx7Bhnq = n2;
  for (i = (As); i < (Nwx7Bhnq); i++) {
    a[i].set(0, 0);
  }
  for (i = (0); i < (Bs); i++) {
    b[i].set(B[i], 0);
  }
  int MNlRFaTx = n2;
  for (i = (Bs); i < (MNlRFaTx); i++) {
    b[i].set(0, 0);
  }
  fft_L(n2, a, mem);
  fft_L(n2, b, mem);
  for (i = (0); i < (n2); i++) {
    a[i] *= b[i];
  }
  fftinv_L(n2, a, mem);
  mul = 1.0 / n2;
  for (i = (0); i < (Rs); i++) {
    res[i] = a[i].x * mul;
  }
}
void convolution_L(double A[], int As, double res[], int Rs, void *mem = wmem) {
  int i;
  int n;
  int n2;
  double mul;
  fft_pnt *a;
  n = max_L(As + As, Rs);
  for (n2 = 1; n2 < n; n2 *= 2) {
    ;
  }
  walloc1d(&a, n2, &mem);
  for (i = (0); i < (As); i++) {
    a[i].set(A[i], 0);
  }
  int vzsjNTAU = n2;
  for (i = (As); i < (vzsjNTAU); i++) {
    a[i].set(0, 0);
  }
  fft_L(n2, a, mem);
  for (i = (0); i < (n2); i++) {
    a[i] *= a[i];
  }
  fftinv_L(n2, a, mem);
  mul = 1.0 / n2;
  for (i = (0); i < (Rs); i++) {
    res[i] = a[i].x * mul;
  }
}
void fft_L(int n, Modint x[], Modint root, void *mem) {
  int i;
  int j;
  int n1;
  int n2;
  int n3;
  int step = 1;
  Modint w1;
  Modint w2;
  Modint w3;
  Modint a;
  Modint b;
  Modint c;
  Modint d;
  Modint aa;
  Modint bb;
  Modint cc;
  Modint dd;
  Modint tmp;
  Modint *y;
  walloc1d(&y, n, &mem);
  tmp = root.pw(((998244353U) - 1) / 4 * 3);
  root = root.pw(((998244353U) - 1) / n);
  while (n > 2) {
    n1 = n / 4;
    n2 = n1 + n1;
    n3 = n1 + n2;
    w1.val = 1;
    for (i = (0); i < (n1); i++) {
      w2 = w1 * w1;
      w3 = w1 * w2;
      for (j = (0); j < (step); j++) {
        a = x[j + step * i];
        b = x[j + step * (i + n1)];
        c = x[j + step * (i + n2)];
        d = x[j + step * (i + n3)];
        aa = a + c;
        bb = a - c;
        cc = b + d;
        dd = (b - d) * tmp;
        y[j + step * (4 * i)] = aa + cc;
        y[j + step * (4 * i + 1)] = w1 * (bb - dd);
        y[j + step * (4 * i + 2)] = w2 * (aa - cc);
        y[j + step * (4 * i + 3)] = w3 * (bb + dd);
      }
      w1 *= root;
    }
    n /= 4;
    step *= 4;
    root *= root;
    root *= root;
    swap(x, y);
  }
  if (n == 2) {
    for (i = (0); i < (step); i++) {
      y[i] = x[i] + x[i + step];
      y[i + step] = x[i] - x[i + step];
    }
    n /= 2;
    step *= 2;
    root *= root;
    swap(x, y);
  }
  for (i = (0); i < (step); i++) {
    y[i] = x[i];
  }
}
void fftinv_L(int n, Modint x[], Modint root, void *mem) {
  int i;
  int j;
  int n1;
  int n2;
  int n3;
  int step = 1;
  Modint w1;
  Modint w2;
  Modint w3;
  Modint a;
  Modint b;
  Modint c;
  Modint d;
  Modint aa;
  Modint bb;
  Modint cc;
  Modint dd;
  Modint tmp;
  Modint *y;
  walloc1d(&y, n, &mem);
  root = root.inverse();
  tmp = root.pw(((998244353U) - 1) / 4);
  root = root.pw(((998244353U) - 1) / n);
  while (n > 2) {
    n1 = n / 4;
    n2 = n1 + n1;
    n3 = n1 + n2;
    w1.val = 1;
    for (i = (0); i < (n1); i++) {
      w2 = w1 * w1;
      w3 = w1 * w2;
      for (j = (0); j < (step); j++) {
        a = x[j + step * i];
        b = x[j + step * (i + n1)];
        c = x[j + step * (i + n2)];
        d = x[j + step * (i + n3)];
        aa = a + c;
        bb = a - c;
        cc = b + d;
        dd = (b - d) * tmp;
        y[j + step * (4 * i)] = aa + cc;
        y[j + step * (4 * i + 1)] = w1 * (bb + dd);
        y[j + step * (4 * i + 2)] = w2 * (aa - cc);
        y[j + step * (4 * i + 3)] = w3 * (bb - dd);
      }
      w1 *= root;
    }
    n /= 4;
    step *= 4;
    root *= root;
    root *= root;
    swap(x, y);
  }
  if (n == 2) {
    for (i = (0); i < (step); i++) {
      y[i] = x[i] + x[i + step];
      y[i + step] = x[i] - x[i + step];
    }
    n /= 2;
    step *= 2;
    root *= root;
    swap(x, y);
  }
  for (i = (0); i < (step); i++) {
    y[i] = x[i];
  }
}
void convolution_L(Modint A[], int As, Modint B[], int Bs, Modint res[], int Rs,
                   Modint root = (3U), void *mem = wmem) {
  int i;
  int n;
  int n2;
  Modint *a;
  Modint *b;
  Modint r;
  n = max_L(As + Bs, Rs);
  for (n2 = 1; n2 < n; n2 *= 2) {
    ;
  }
  walloc1d(&a, n2, &mem);
  walloc1d(&b, n2, &mem);
  for (i = (0); i < (As); i++) {
    a[i] = A[i];
  }
  int w54A8_wh = n2;
  for (i = (As); i < (w54A8_wh); i++) {
    a[i].val = 0;
  }
  for (i = (0); i < (Bs); i++) {
    b[i] = B[i];
  }
  int Zs_a1Ftk = n2;
  for (i = (Bs); i < (Zs_a1Ftk); i++) {
    b[i].val = 0;
  }
  fft_L(n2, a, root, mem);
  fft_L(n2, b, root, mem);
  for (i = (0); i < (n2); i++) {
    a[i] *= b[i];
  }
  fftinv_L(n2, a, root, mem);
  r = Modint(n2).inverse();
  for (i = (0); i < (Rs); i++) {
    res[i] = a[i] * r;
  }
}
void convolution_L(Modint A[], int As, Modint res[], int Rs, Modint root = (3U),
                   void *mem = wmem) {
  int i;
  int n;
  int n2;
  Modint *a;
  Modint r;
  n = max_L(2 * As, Rs);
  for (n2 = 1; n2 < n; n2 *= 2) {
    ;
  }
  walloc1d(&a, n2, &mem);
  for (i = (0); i < (As); i++) {
    a[i] = A[i];
  }
  int Ly6DsuN0 = n2;
  for (i = (As); i < (Ly6DsuN0); i++) {
    a[i].val = 0;
  }
  fft_L(n2, a, root, mem);
  for (i = (0); i < (n2); i++) {
    a[i] *= a[i];
  }
  fftinv_L(n2, a, root, mem);
  r = Modint(n2).inverse();
  for (i = (0); i < (Rs); i++) {
    res[i] = a[i] * r;
  }
}
int N;
int H[100000];
int sz;
int hist[100000 + 1];
int len[100000];
Modint *arr[100000];
Modint *nx;
Modint df[100000 + 10];
int main() {
  int i;
  wmem = memarr;
  int mx;
  int x;
  int y;
  Modint res = 0;
  LHeap<int> hp;
  Comb<Modint> c;
  df[0] = df[1] = 1;
  for (i = (2); i < (100000 + 10); i++) {
    df[i] = i * df[i - 2];
  }
  rd(N);
  {
    int Q5VJL1cS;
    for (Q5VJL1cS = (0); Q5VJL1cS < (2 * N); Q5VJL1cS++) {
      rd(H[Q5VJL1cS]);
      H[Q5VJL1cS] += (-1);
    }
  }
  for (i = (0); i < (2 * N); i++) {
    hist[H[i]]++;
  }
  rsortA_L(100000, hist);
  while (hist[sz] > 1) {
    sz++;
  }
  if (hist[0] > N) {
    wt_L(0);
    wt_L('\n');
    return 0;
  }
  if (sz == 0) {
    wt_L(df[2 * N - 1]);
    wt_L('\n');
    return 0;
  }
  for (i = (0); i < (sz); i++) {
    int j;
    len[i] = hist[i] / 2 + 1;
    walloc1d(&arr[i], len[i]);
    arr[i][0] = 1;
    for (j = (1); j < (len[i]); j++) {
      arr[i][j] = c.C(hist[i], 2 * j) * df[2 * j - 1];
    }
  }
  hp.walloc(sz);
  hp.init(sz);
  for (i = (0); i < (sz); i++) {
    hp.change(i, len[i]);
  }
  while (hp.size > 1) {
    x = hp.pop();
    y = hp.pop();
    walloc1d(&nx, len[x] + len[y] - 1);
    convolution_L(arr[x], len[x], arr[y], len[y], nx, len[x] + len[y] - 1);
    arr[x] = nx;
    len[x] = len[x] + len[y] - 1;
    hp.change(x, len[x] + len[y] - 1);
  }
  x = hp.pop();
  for (i = (0); i < (len[x]); i++) {
    if (2 * N - 1 - 2 * i >= 0) {
      if (i % 2 == 0) {
        res += arr[x][i] * df[2 * N - 1 - 2 * i];
      } else {
        res -= arr[x][i] * df[2 * N - 1 - 2 * i];
      }
    }
  }
  wt_L(res);
  wt_L('\n');
  return 0;
}
