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>
#pragma GCC optimize("Ofast")
namespace in {
char buf[1 << 21], *p1 = buf, *p2 = buf;
inline int getc() {
  return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)
             ? EOF
             : *p1++;
}
template <typename T>
inline void read(T &t) {
  t = 0;
  int f = 0;
  char ch = getc();
  while (!isdigit(ch)) {
    if (ch == '-') f = 1;
    ch = getc();
  }
  while (isdigit(ch)) {
    t = t * 10 + ch - 48;
    ch = getc();
  }
  if (f) t = -t;
}
template <typename T, typename... Args>
inline void read(T &t, Args &...args) {
  read(t);
  read(args...);
}
}  // namespace in
namespace out {
char buffer[1 << 21];
int p1 = -1;
const int p2 = (1 << 21) - 1;
inline void flush() { fwrite(buffer, 1, p1 + 1, stdout), p1 = -1; }
inline void putc(const char &x) {
  if (p1 == p2) flush();
  buffer[++p1] = x;
}
template <typename T>
void write(T x) {
  static char buf[15];
  static int len = -1;
  if (x >= 0) {
    do {
      buf[++len] = x % 10 + 48, x /= 10;
    } while (x);
  } else {
    putc('-');
    do {
      buf[++len] = -(x % 10) + 48, x /= 10;
    } while (x);
  }
  while (len >= 0) putc(buf[len]), --len;
}
}  // namespace out
using namespace std;
template <const int mod>
struct modint {
  int x;
  modint<mod>(int o = 0) { x = o; }
  modint<mod> &operator=(int o) { return x = o, *this; }
  modint<mod> &operator+=(modint<mod> o) {
    return x = x + o.x >= mod ? x + o.x - mod : x + o.x, *this;
  }
  modint<mod> &operator-=(modint<mod> o) {
    return x = x - o.x < 0 ? x - o.x + mod : x - o.x, *this;
  }
  modint<mod> &operator*=(modint<mod> o) {
    return x = 1ll * x * o.x % mod, *this;
  }
  modint<mod> &operator^=(int b) {
    modint<mod> a = *this, c = 1;
    for (; b; b >>= 1, a *= a)
      if (b & 1) c *= a;
    return x = c.x, *this;
  }
  modint<mod> &operator/=(modint<mod> o) { return *this *= o ^= mod - 2; }
  modint<mod> &operator+=(int o) {
    return x = x + o >= mod ? x + o - mod : x + o, *this;
  }
  modint<mod> &operator-=(int o) {
    return x = x - o < 0 ? x - o + mod : x - o, *this;
  }
  modint<mod> &operator*=(int o) { return x = 1ll * x * o % mod, *this; }
  modint<mod> &operator/=(int o) {
    return *this *= ((modint<mod>(o)) ^= mod - 2);
  }
  template <class I>
  friend modint<mod> operator+(modint<mod> a, I b) {
    return a += b;
  }
  template <class I>
  friend modint<mod> operator-(modint<mod> a, I b) {
    return a -= b;
  }
  template <class I>
  friend modint<mod> operator*(modint<mod> a, I b) {
    return a *= b;
  }
  template <class I>
  friend modint<mod> operator/(modint<mod> a, I b) {
    return a /= b;
  }
  friend modint<mod> operator^(modint<mod> a, int b) { return a ^= b; }
  friend bool operator==(modint<mod> a, int b) { return a.x == b; }
  friend bool operator!=(modint<mod> a, int b) { return a.x != b; }
  bool operator!() { return !x; }
  modint<mod> operator-() { return x ? mod - x : 0; }
  modint<mod> &operator++(int) { return *this += 1; }
};
const int N = 4e6 + 5;
const int mod = 998244353;
const modint<mod> GG = 3, Ginv = modint<mod>(1) / 3, I = 86583718;
struct poly {
  vector<modint<mod>> a;
  modint<mod> &operator[](int i) { return a[i]; }
  int size() { return a.size(); }
  void print() {
    for (int i = 0; i < size(); i++) printf("%d ", a[i]);
    printf("\n");
  }
  void resize(int n) { a.resize(n); }
  void reverse() { std::reverse(a.begin(), a.end()); }
};
int rev[N];
inline int ext(int n) {
  int k = 0;
  while ((1 << k) < n) k++;
  return k;
}
inline void init(int k) {
  int n = 1 << k;
  for (int i = 0; i < n; i++)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (k - 1));
}
inline void ntt(poly &a, int k, int typ) {
  int n = 1 << k;
  for (int i = 0; i < n; i++)
    if (i < rev[i]) swap(a[i], a[rev[i]]);
  for (int mid = 1; mid < n; mid <<= 1) {
    modint<mod> wn = (typ > 0 ? GG : Ginv) ^ ((mod - 1) / (mid << 1));
    for (int r = mid << 1, j = 0; j < n; j += r) {
      modint<mod> w = 1;
      for (int k = 0; k < mid; k++, w = w * wn) {
        modint<mod> x = a[j + k], y = w * a[j + k + mid];
        a[j + k] = x + y, a[j + k + mid] = x - y;
      }
    }
  }
  if (typ < 0) {
    modint<mod> inv = modint<mod>(1) / n;
    for (int i = 0; i < n; i++) a[i] *= inv;
  }
}
inline poly one() {
  poly a;
  a.a.push_back(1);
  return a;
}
poly operator+(poly a, poly b) {
  int n = max(a.size(), b.size());
  a.resize(n), b.resize(n);
  for (int i = 0; i < n; i++) a[i] += b[i];
  return a;
}
poly operator-(poly a, poly b) {
  int n = max(a.size(), b.size());
  a.resize(n), b.resize(n);
  for (int i = 0; i < n; i++) a[i] -= b[i];
  return a;
}
inline poly operator*(poly a, poly b) {
  int n = a.size() + b.size() - 1, k = ext(n);
  a.resize(1 << k), b.resize(1 << k), init(k);
  ntt(a, k, 1);
  ntt(b, k, 1);
  for (int i = 0; i < (1 << k); i++) a[i] *= b[i];
  ntt(a, k, -1), a.resize(n);
  return a;
}
inline poly operator*(poly a, modint<mod> b) {
  for (int i = 0; i < a.size(); i++) a[i] *= b;
  return a;
}
inline poly operator/(poly a, modint<mod> b) {
  for (int i = 0; i < a.size(); i++) a[i] /= b;
  return a;
}
inline poly operator-(poly a) {
  for (int i = 0; i < a.size(); i++) a[i] = -a[i];
  return a;
}
poly inv(poly F, int k) {
  int n = 1 << k;
  F.resize(n);
  if (n == 1) {
    F[0] = modint<mod>(1) / F[0];
    return F;
  }
  poly G, H = inv(F, k - 1);
  G.resize(n), H.resize(n << 1), F.resize(n << 1);
  for (int i = 0; i < n / 2; i++) G[i] = H[i] * 2;
  init(k + 1), ntt(H, k + 1, 1), ntt(F, k + 1, 1);
  for (int i = 0; i < (n << 1); i++) H[i] = H[i] * H[i] * F[i];
  ntt(H, k + 1, -1), H.resize(n);
  for (int i = 0; i < n; i++) G[i] -= H[i];
  return G;
}
inline poly inv(poly a) {
  int n = a.size();
  a = inv(a, ext(n)), a.resize(n);
  return a;
  ;
}
inline poly deriv(poly a) {
  int n = a.size() - 1;
  for (int i = 0; i < n; i++) a[i] = a[i + 1] * (i + 1);
  a.resize(n);
  return a;
}
inline poly inter(poly a) {
  int n = a.size() + 1;
  a.resize(n);
  for (int i = n; i >= 1; i--) a[i] = a[i - 1] / i;
  a[0] = 0;
  return a;
}
inline poly ln(poly a) {
  int n = a.size();
  a = inter(deriv(a) * inv(a));
  a.resize(n);
  return a;
}
poly exp(poly a, int k) {
  int n = 1 << k;
  a.resize(n);
  if (n == 1) return one();
  poly f0 = exp(a, k - 1);
  f0.resize(n);
  return f0 * (one() + a - ln(f0));
}
poly exp(poly a) {
  int n = a.size();
  a = exp(a, ext(n));
  a.resize(n);
  return a;
}
inline poly pow(poly a, modint<mod> k) {
  a = ln(a);
  for (int i = 0; i < a.size(); i++) a[i] *= k.x;
  return exp(a);
}
poly divx(poly f) {
  if (f[0] != 0) exit(-1);
  for (int i = 0; i < f.size() - 2; i++) f[i] = f[i + 1];
  f.resize(f.size() - 1);
  return f;
}
poly mulx(poly f) {
  int n = f.size();
  f.resize(n + 1);
  for (int i = n; i; i--) f[i] = f[i - 1];
  f[0] = 0;
  return f;
}
int n;
modint<mod> fac[N], ifac[N];
modint<mod> f[N];
signed main() {
  fac[0] = 1;
  for (int i = 1; i < N; i++) fac[i] = fac[i - 1] * i;
  ifac[N - 1] = modint<mod>(1) / fac[N - 1];
  for (int i = N - 1; i; i--) ifac[i - 1] = ifac[i] * i;
  scanf("%d", &n);
  poly F, P, H;
  F.resize(n + 5);
  P.resize(n + 5);
  H.resize(n + 5);
  for (int i = 1; i < F.size(); i++) F[i] = ifac[i];
  F = divx(F);
  F = -F;
  F[0] = F[0] + 1;
  F = divx(F);
  F = inv(F);
  for (int i = 1; i < P.size(); i++)
    if (i & 1)
      P[i] = modint<mod>(1) / i;
    else
      P[i] = -modint<mod>(1) / i;
  H = inv(divx(P));
  poly KK = -H;
  KK[0]++;
  KK = divx(KK);
  KK = inv(KK);
  poly tmp = pow(H, n + 1);
  poly tmp1 = tmp * KK;
  poly tmp2 = deriv(H) * tmp;
  tmp2.resize(n + 5);
  tmp2 = tmp2 * KK;
  tmp2.resize(n + 5);
  tmp2 = tmp2 * KK;
  for (int j = 1; j <= n + 1; j++) {
    int m = n - j + 1;
    f[j] = F[j + 1] - (modint<mod>(1) / (n + 1)) *
                          (tmp2[n - m + 2] + (tmp1[n - m + 2] * m));
  }
  poly a, b;
  a.resize(n);
  b.resize(n);
  for (int j = 0; j < n; j++) a[n - j - 1] = fac[j] * f[j];
  for (int j = 0; j < n; j++)
    if (j & 1)
      b[j] = -ifac[j];
    else
      b[j] = ifac[j];
  a = a * b;
  a.resize(n);
  {
    modint<mod> tmp = 0;
    for (int i = 1; i <= n; i++) tmp += fac[n] * ifac[i];
    out::write(tmp.x);
    out::putc(' ');
  }
  for (int k = 1; k < n; k++) {
    modint<mod> ans = fac[n] * ifac[k];
    ans *= a[n - k - 1];
    out::write(ans.x);
    out::putc(' ');
  }
  out::flush();
}