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>
char obuf[1 << 21], *oS = obuf, *oT = oS + (1 << 21) - 1;
struct Flusher_ {
  ~Flusher_() { (fwrite(obuf, 1, oS - obuf, stdout), oS = obuf, void()); }
} flusher_;
template <class T>
inline void print(T x) {
  if (x < 0)
    (*oS++ = ('-'),
     oS == oT ? (fwrite(obuf, 1, oS - obuf, stdout), oS = obuf, void())
              : void()),
        x = -x;
  if (x > 9) print(x / 10);
  (*oS++ = (x % 10 + '0'),
   oS == oT ? (fwrite(obuf, 1, oS - obuf, stdout), oS = obuf, void()) : void());
}
template <class T>
inline void print(T x, char c) {
  print(x), (*oS++ = (c),
             oS == oT ? (fwrite(obuf, 1, oS - obuf, stdout), oS = obuf, void())
                      : void());
}
const int N = 1e5 + 10, wyp = 998244353;
int n, len;
struct z {
  int32_t x;
  z(int32_t x = 0) : x(x) {}
  friend inline z operator*(z a, z b) { return (int64_t)a.x * b.x % wyp; }
  friend inline z operator-(z a, z b) {
    return (a.x -= b.x) < 0 ? a.x + wyp : a.x;
  }
  friend inline z operator+(z a, z b) {
    return (a.x += b.x) >= wyp ? a.x - wyp : a.x;
  }
} h[N], ans[N], inv[N], fac[N], ifac[N];
inline z fpow(z a, int b) {
  z s = 1;
  for (; b; b >>= 1, a = a * a)
    if (b & 1) s = s * a;
  return s;
}
void init(int n) {
  fac[0] = ifac[0] = inv[0] = inv[1] = 1;
  for (int i = 2; i < n; i++) inv[i] = (wyp - wyp / i) * inv[wyp % i];
  for (int i = 1; i < n; i++)
    fac[i] = fac[i - 1] * i, ifac[i] = ifac[i - 1] * inv[i];
}
namespace poly {
int len = 1, rev[N << 2];
z w[N << 2];
struct vec : std::vector<z> {
  using std::vector<z>::vector;
  inline void input() {
    for (size_t i = 0; i < size(); i++)
      scanf("%d", &((int &)this->operator[](i)));
  }
  inline void output() {
    for (size_t i = 0; i < size(); i++)
      printf("%d%c", this->operator[](i).x, " \n"[i + 1 == size()]);
  }
  inline vec divx() {
    vec res = *this;
    return res.erase(res.begin()), res;
  }
  inline vec setl(size_t len) {
    vec res = *this;
    return res.resize(len), res;
  }
  inline vec fun1() {
    vec res(this->begin() + 1, this->end());
    for (int i = 0; i < res.size(); i++) res[i].x = wyp - res[i].x;
    return res;
  }
};
int init(int n) {
  int lim = 1, k = 0;
  while (lim < n) lim <<= 1, ++k;
  for (int i = 0; i < lim; i++)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (k - 1));
  for (; len < lim; len <<= 1) {
    z wn = fpow(3, (wyp - 1) / (len << 1));
    w[len] = 1;
    for (int i = 1; i < len; i++) w[i + len] = w[i + len - 1] * wn;
  }
  return lim;
}
void dft(vec &a, int lim) {
  a.resize(lim);
  for (int i = 0; i < lim; i++)
    if (i < rev[i]) std::swap(a[i], a[rev[i]]);
  for (int i = 0; i < lim; i += 2) {
    z x = a[i], y = a[i + 1] * w[1];
    a[i] = x + y, a[i + 1] = x - y;
  }
  for (int len = 2; len < lim; len <<= 1)
    for (int i = 0; i < lim; i += (len << 1))
      for (int j = 0; j < len; j++) {
        z x = a[i + j], y = a[i + j + len] * w[j + len];
        a[i + j] = x + y, a[i + j + len] = x - y;
      }
}
void idft(vec &a, int lim) {
  z inv = fpow(lim, wyp - 2);
  dft(a, lim), std::reverse(&a[1], &a[lim]);
  for (int i = 0; i < lim; i++) a[i] = a[i] * inv;
}
vec operator+(vec a, const vec &b) {
  a.resize(std::max(a.size(), b.size()));
  for (int i = 0; i < b.size(); i++) a[i] = a[i] + b[i];
  return a;
}
vec operator-(vec a, const vec &b) {
  a.resize(std::max(a.size(), b.size()));
  for (int i = 0; i < b.size(); i++) a[i] = a[i] - b[i];
  return a;
}
vec operator*(vec a, vec b) {
  if (a.size() < 20 || b.size() < 20 || (uint64_t)a.size() + b.size() < 400) {
    vec c(a.size() + b.size() - 1);
    for (int i = 0; i < a.size(); i++)
      for (int j = 0; j < b.size(); j++) c[i + j] = c[i + j] + a[i] * b[j];
    return c;
  }
  int len = a.size() + b.size() - 1, lim = init(len);
  dft(a, lim), dft(b, lim);
  for (int i = 0; i < lim; i++) a[i] = a[i] * b[i];
  return idft(a, lim), a.resize(len), a;
}
vec inv(const vec &f, int len = -1) {
  if ((len = ~len ? len : f.size()) == 1) return vec{fpow(f[0], wyp - 2)};
  vec a = inv(f, (len + 1) >> 1), b(&f[0], &f[len]);
  int lim = init((len << 1) - 1);
  dft(a, lim), dft(b, lim);
  for (int i = 0; i < lim; i++) a[i] = a[i] * (2 - a[i] * b[i]);
  return idft(a, lim), a.resize(len), a;
}
vec inte(vec a) {
  for (int i = a.size() - 1; i; i--) a[i] = a[i - 1] * ::inv[i];
  return *a.begin() = 0, a;
}
vec deri(vec a) {
  for (int i = 0; i < a.size() - 1; i++) a[i] = a[i + 1] * (i + 1);
  return *a.rbegin() = 0, a;
}
vec ln(const vec &f) { return inte((deri(f) * inv(f)).setl(f.size())); }
vec exp(const vec &f, int len = -1) {
  if ((len = ~len ? len : f.size()) == 1) return vec{1};
  vec a = exp(f, (len + 1) >> 1), b = a;
  b.resize(len), b = ln(b);
  for (int i = 0; i < len; i++) b[i] = 0 - b[i];
  b[0] = b[0] + 1;
  for (int i = 0; i < len; i++) b[i] = b[i] + f[i];
  return (a * b).setl(len);
}
vec pow(vec a, int b) {
  a = ln(a);
  for (int i = 0; i < a.size(); i++) a[i] = a[i] * b;
  return exp(a);
}
}  // namespace poly
using poly::vec;
int main() {
  std::cin >> n;
  init(n + 10), len = n + 5;
  vec Fexp(ifac + 1, ifac + len + 1);
  vec Finv = Fexp * poly::inv(Fexp.fun1());
  for (int i = 0; i <= n; i++) h[i] = Finv[i + 1];
  vec P(len);
  for (int i = 0; i < len; i++) P[i] = (i & 1 ? wyp - 1 : 1) * inv[i + 1];
  P = poly::inv(P);
  vec Ppow = poly::pow(P, n + 1);
  vec Pinv = poly::inv(P.fun1());
  vec lpart = (Ppow * Pinv).setl(len);
  vec rpart = ((poly::deri(P) * Pinv).setl(len) * lpart).setl(len);
  z tmp = fpow(n + 1, wyp - 2);
  for (int i = 0; i <= n; i++)
    h[i] = h[i] - tmp * (lpart[i + 1] * (n - i + 1) + rpart[i + 1]);
  vec f(n + 1), g(n + 1);
  for (int i = 0; i <= n; i++) f[i] = ((n - i) & 1 ? wyp - 1 : 1) * ifac[n - i];
  for (int i = 0; i <= n; i++) g[i] = fac[i] * h[i];
  f = f * g;
  for (int i = 0; i < n; i++) ans[i] = f[i + n] * fac[n] * ifac[i];
  for (int i = 0; i < n; i++) print(ans[i].x, " \n"[i + 1 == n]);
}