Problem: Note that the only differences between easy and hard versions are the constraints on n and the time limit. You can make hacks only if all versions are solved.

Slime is interested in sequences. He defined good positive integer sequences p of length n as follows:

  * For each k>1 that presents in p, there should be at least one pair of indices i,j, such that 1 ≤ i < j ≤ n, p_i = k - 1 and p_j = k.



For the given integer n, the set of all good sequences of length n is s_n. For the fixed integer k and the sequence p, let f_p(k) be the number of times that k appears in p. For each k from 1 to n, Slime wants to know the following value:

$$$\left(∑_{p∈ s_n} f_p(k)\right)\ mod\ 998 244 353$$$

Input

The first line contains one integer n\ (1≤ n≤ 5000).

Output

Print n integers, the i-th of them should be equal to \left(∑_{p∈ s_n} f_p(i)\right)\ mod\ 998 244 353.

Examples

Input


2


Output


3 1 


Input


3


Output


10 7 1 


Input


1


Output


1 

Note

In the first example, s=\{[1,1],[1,2]\}.

In the second example, s=\{[1,1,1],[1,1,2],[1,2,1],[1,2,2],[2,1,2],[1,2,3]\}.

In the third example, s=\{[1]\}.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
template <typename T>
void pfill(T* pst, const T* ped, T val) {
  for (; pst != ped; *(pst++) = val)
    ;
}
template <typename T>
void pcopy(T* pst, const T* ped, T* pval) {
  for (; pst != ped; *(pst++) = *(pval++))
    ;
}
const int N = 262144;
const int Mod = 998244353;
const int bzmax = 19;
const int g = 3;
void exgcd(int a, int b, int& x, int& y) {
  if (!b) {
    x = 1, y = 0;
  } else {
    exgcd(b, a % b, y, x);
    y -= (a / b) * x;
  }
}
int inv(int a, int Mod) {
  int x, y;
  exgcd(a, Mod, x, y);
  return (x < 0) ? (x + Mod) : (x);
}
template <const int Mod = ::Mod>
class Z {
 public:
  int v;
  Z() : v(0) {}
  Z(int x) : v(x) {}
  Z(long long x) : v(x % Mod) {}
  friend Z operator+(const Z& a, const Z& b) {
    int x;
    return Z(((x = a.v + b.v) >= Mod) ? (x - Mod) : (x));
  }
  friend Z operator-(const Z& a, const Z& b) {
    int x;
    return Z(((x = a.v - b.v) < 0) ? (x + Mod) : (x));
  }
  friend Z operator*(const Z& a, const Z& b) { return Z(a.v * 1ll * b.v); }
  friend Z operator~(const Z& a) { return inv(a.v, Mod); }
  friend Z operator-(const Z& a) { return Z(0) - a; }
  Z& operator+=(Z b) { return *this = *this + b; }
  Z& operator-=(Z b) { return *this = *this - b; }
  Z& operator*=(Z b) { return *this = *this * b; }
  friend bool operator==(const Z& a, const Z& b) { return a.v == b.v; }
};
Z<> qpow(Z<> a, int p) {
  if (p < Mod - 1) p += Mod - 1;
  Z<> rt = 1, pa = a;
  for (; p; p >>= 1, pa = pa * pa) {
    if (p & 1) {
      rt = rt * pa;
    }
  }
  return rt;
}
const Z<> inv2((Mod + 1) >> 1);
class NTT {
 private:
  Z<> gn[bzmax + 4], _gn[bzmax + 4];

 public:
  NTT() {
    for (int i = 0; i <= bzmax; i++) {
      gn[i] = qpow(Z<>(g), (Mod - 1) >> i);
      _gn[i] = qpow(Z<>(g), -((Mod - 1) >> i));
    }
  }
  void operator()(Z<>* f, int len, int sgn) {
    for (int i = 1, j = len >> 1, k; i < len - 1; i++, j += k) {
      if (i < j) swap(f[i], f[j]);
      for (k = len >> 1; k <= j; j -= k, k >>= 1)
        ;
    }
    Z<>*wn = (sgn > 0) ? (gn + 1) : (_gn + 1), w, a, b;
    for (int l = 2, hl; l <= len; l <<= 1, wn++) {
      hl = l >> 1, w = 1;
      for (int i = 0; i < len; i += l, w = 1) {
        for (int j = 0; j < hl; j++, w *= *wn) {
          a = f[i + j], b = f[i + j + hl] * w;
          f[i + j] = a + b;
          f[i + j + hl] = a - b;
        }
      }
    }
    if (sgn < 0) {
      Z<> invlen = ~Z<>(len);
      for (int i = 0; i < len; i++) {
        f[i] *= invlen;
      }
    }
  }
  int correct_len(int len) {
    int m = 1;
    for (; m <= len; m <<= 1)
      ;
    return m;
  }
} NTT;
void pol_inverse(Z<>* f, Z<>* g, int n) {
  static Z<> A[N];
  if (n == 1) {
    g[0] = ~f[0];
  } else {
    int hn = (n + 1) >> 1, t = NTT.correct_len(n << 1 | 1);
    pol_inverse(f, g, hn);
    pcopy(A, A + n, f);
    pfill(A + n, A + t, Z<>(0));
    pfill(g + hn, g + t, Z<>(0));
    NTT(A, t, 1);
    NTT(g, t, 1);
    for (int i = 0; i < t; i++) {
      g[i] = g[i] * (Z<>(2) - g[i] * A[i]);
    }
    NTT(g, t, -1);
    pfill(g + n, g + t, Z<>(0));
  }
}
void pol_sqrt(Z<>* f, Z<>* g, int n) {
  static Z<> A[N], B[N];
  if (n == 1) {
    g[0] = f[0];
  } else {
    int hn = (n + 1) >> 1, t = NTT.correct_len(n + n);
    pol_sqrt(f, g, hn);
    pfill(g + hn, g + n, Z<>(0));
    for (int i = 0; i < hn; i++) A[i] = g[i] + g[i];
    pfill(A + hn, A + t, Z<>(0));
    pol_inverse(A, B, n);
    pcopy(A, A + n, f);
    pfill(A + n, A + t, Z<>(0));
    NTT(A, t, 1);
    NTT(B, t, 1);
    for (int i = 0; i < t; i++) A[i] *= B[i];
    NTT(A, t, -1);
    for (int i = 0; i < n; i++) g[i] = g[i] * inv2 + A[i];
  }
}
typedef class Poly : public vector<Z<> > {
 public:
  using vector<Z<> >::vector;
  Poly& fix(int sz) {
    resize(sz);
    return *this;
  }
} Poly;
Poly operator+(Poly A, Poly B) {
  int n = A.size(), m = B.size();
  int t = max(n, m);
  A.resize(t), B.resize(t);
  for (int i = 0; i < t; i++) {
    A[i] += B[i];
  }
  return A;
}
Poly operator-(Poly A, Poly B) {
  int n = A.size(), m = B.size();
  int t = max(n, m);
  A.resize(t), B.resize(t);
  for (int i = 0; i < t; i++) {
    A[i] -= B[i];
  }
  return A;
}
Poly sqrt(Poly a) {
  Poly rt(a.size());
  pol_sqrt(a.data(), rt.data(), a.size());
  return rt;
}
Poly operator*(Poly A, Poly B) {
  int n = A.size(), m = B.size();
  int k = NTT.correct_len(n + m - 1);
  if (n < 20 || m < 20) {
    Poly rt(n + m - 1);
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        rt[i + j] += A[i] * B[j];
      }
    }
    return rt;
  }
  A.resize(k), B.resize(k);
  NTT(A.data(), k, 1);
  NTT(B.data(), k, 1);
  for (int i = 0; i < k; i++) {
    A[i] *= B[i];
  }
  NTT(A.data(), k, -1);
  A.resize(n + m - 1);
  return A;
}
Poly operator~(Poly f) {
  int n = f.size(), t = NTT.correct_len((n << 1) | 1);
  Poly rt(t);
  f.resize(t);
  pol_inverse(f.data(), rt.data(), n);
  rt.resize(n);
  return rt;
}
Poly operator/(Poly A, Poly B) {
  int n = A.size(), m = B.size();
  if (n < m) {
    return Poly{0};
  }
  int r = n - m + 1;
  reverse(A.begin(), A.end());
  reverse(B.begin(), B.end());
  A.resize(r), B.resize(r);
  A = A * ~B;
  A.resize(r);
  reverse(A.begin(), A.end());
  return A;
}
Poly operator%(Poly A, Poly B) {
  int n = A.size(), m = B.size();
  if (n < m) {
    return A;
  }
  if (m == 1) {
    return Poly{0};
  }
  A = A - A / B * B;
  A.resize(m - 1);
  return A;
}
Z<> Inv[N];
void init_inv(int n) {
  Inv[0] = 0, Inv[1] = 1;
  for (int i = 2; i <= n; i++) {
    Inv[i] = Inv[Mod % i] * Z<>((Mod - (Mod / i)));
  }
}
void diff(Poly& f) {
  if (f.size() == 1) {
    f[0] = 0;
    return;
  }
  for (int i = 1; i < (signed)f.size(); i++) {
    f[i - 1] = f[i] * Z<>(i);
  }
  f.resize(f.size() - 1);
}
void integ(Poly& f) {
  f.resize(f.size() + 1);
  for (int i = (signed)f.size() - 1; i; i--) {
    f[i] = f[i - 1] * Inv[i];
  }
  f[0] = 0;
}
Poly Diff(Poly f) {
  diff(f);
  return f;
}
Poly Integ(Poly f) {
  integ(f);
  return f;
}
Poly ln(Poly f) {
  int n = f.size();
  Poly h = f;
  diff(h);
  f = h * ~f;
  f.resize(n - 1);
  integ(f);
  return f;
}
void pol_exp(Poly& f, Poly& g, int n) {
  Poly h;
  if (n == 1) {
    g.resize(1);
    g[0] = 1;
  } else {
    int hn = (n + 1) >> 1;
    pol_exp(f, g, hn);
    h.resize(n), g.resize(n);
    pcopy(h.data(), h.data() + n, f.data());
    g = g * (Poly{1} - ln(g) + h);
    g.resize(n);
  }
}
Poly exp(Poly f) {
  int n = f.size();
  Poly rt;
  pol_exp(f, rt, n);
  return rt;
}
Poly remove_front(Poly x) {
  assert(!x.empty());
  x.erase(x.begin());
  return x;
}
int n;
Poly fac, _fac;
void prepare(int n) {
  fac.resize(n + 1);
  _fac.resize(n + 1);
  fac[0] = 1;
  for (int i = 1; i <= n; i++) {
    fac[i] = fac[i - 1] * i;
  }
  _fac[n] = ~fac[n];
  for (int i = n; i; i--) {
    _fac[i - 1] = _fac[i] * i;
  }
}
Poly work() {
  Poly f = ~remove_front(ln((Poly{1, 1}).fix(n + 3)));
  Poly fn = exp(ln(f) * Poly{n + 1});
  Poly g = ~remove_front(Poly{1} - f);
  Poly a = (fn * g).fix(n + 1);
  g = (g * g).fix(n + 1);
  Poly b = ((fn * Diff(f)).fix(n + 1) * g).fix(n + 1);
  Poly h(n);
  Z<> coef = ~Z<>(n + 1);
  for (int i = 0; i < n; i++) {
    h[i] = (a[i + 1] * (n - i + 1) + b[i + 1]) * coef;
  }
  Poly F(_fac.begin() + 1, _fac.begin() + n + 2);
  h = remove_front((F * ~remove_front(Poly{1} - F)).fix(n + 1)) - h;
  h[n - 1] = _fac[n];
  return h;
}
int main() {
  scanf("%d", &n);
  init_inv(n + 3);
  prepare(n + 3);
  Poly f = work();
  Poly g(n);
  for (int i = 0; i < n; i++) {
    f[i] *= fac[i];
  }
  for (int i = 0; i < n; i++) {
    g[i] = _fac[i];
    if (i & 1) {
      g[i] = -g[i];
    }
  }
  reverse(g.begin(), g.end());
  f = f * g;
  for (int i = 0; i < n; i++) {
    Z<> ans = f[i + n - 1] * fac[n] * _fac[i];
    printf("%d ", ans.v);
  }
  return 0;
}