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;
const int RLEN = 1 << 20 | 1;
inline char gc() {
  static char ibuf[RLEN], *ib, *ob;
  (ib == ob) && (ob = (ib = ibuf) + fread(ibuf, 1, RLEN, stdin));
  return (ib == ob) ? EOF : *ib++;
}
inline int read() {
  char ch = gc();
  int res = 0;
  bool f = 1;
  while (!isdigit(ch)) f ^= ch == '-', ch = gc();
  while (isdigit(ch)) res = (res + (res << 2) << 1) + (ch ^ 48), ch = gc();
  return f ? res : -res;
}
inline long long readll() {
  char ch = gc();
  long long res = 0;
  bool f = 1;
  while (!isdigit(ch)) f ^= ch == '-', ch = gc();
  while (isdigit(ch)) res = (res + (res << 2) << 1) + (ch ^ 48), ch = gc();
  return f ? res : -res;
}
inline char readchar() {
  char ch = gc();
  while (isspace(ch)) ch = gc();
  return ch;
}
inline int readstring(char *s) {
  int top = 0;
  char ch = gc();
  while (isspace(ch)) ch = gc();
  while (!isspace(ch) && ch != EOF) s[++top] = ch, ch = gc();
  s[top + 1] = '\0';
  return top;
}
template <typename tp>
inline void chemx(tp &a, tp b) {
  a = max(a, b);
}
template <typename tp>
inline void chemn(tp &a, tp b) {
  a = min(a, b);
}
const int mod = 998244353;
inline int add(int a, int b) {
  return (a + b) >= mod ? (a + b - mod) : (a + b);
}
inline int dec(int a, int b) { return (a < b) ? (a - b + mod) : (a - b); }
inline int mul(int a, int b) {
  static long long r;
  r = (long long)a * b;
  return (r >= mod) ? (r % mod) : r;
}
inline void Add(int &a, int b) { a = (a + b) >= mod ? (a + b - mod) : (a + b); }
inline void Dec(int &a, int b) { a = (a < b) ? (a - b + mod) : (a - b); }
inline void Mul(int &a, int b) {
  static long long r;
  r = (long long)a * b;
  a = (r >= mod) ? (r % mod) : r;
}
inline int ksm(int a, int b, int res = 1) {
  for (; b; b >>= 1, Mul(a, a)) (b & 1) && (Mul(res, a), 1);
  return res;
}
inline int Inv(int x) { return ksm(x, mod - 2); }
inline int fix(long long x) {
  x %= mod;
  return (x < 0) ? x + mod : x;
}
const int N = 200051;
int fac[N], ifac[N];
inline void init_fac() {
  fac[0] = ifac[0] = 1;
  for (int i = 1; i < N; i++) fac[i] = mul(fac[i - 1], i);
  ifac[N - 1] = Inv(fac[N - 1]);
  for (int i = N - 2; i; i--) ifac[i] = mul(ifac[i + 1], i + 1);
}
inline int Cb(int n, int m) {
  return (n < 0 || m < 0 || n < 0) ? 0 : mul(fac[n], mul(ifac[m], ifac[n - m]));
}
namespace Poly {
const int C = 19, M = (1 << C) | 5;
int *w[C + 1], rev[M], iv[M];
inline void init_rev(int lim) {
  for (int i = 0; i < lim; i++)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) * (lim >> 1));
}
inline void init_w() {
  for (int i = 1; i <= C; i++) w[i] = new int[(1 << (i - 1)) | 1];
  int wn = ksm(3, (mod - 1) / (1 << C));
  w[C][0] = 1;
  for (int i = 1, l = 1 << (C - 1); i < l; i++) w[C][i] = mul(w[C][i - 1], wn);
  for (int i = C - 1; i; i--)
    for (int j = 0, l = 1 << (i - 1); j < l; j++) w[i][j] = w[i + 1][j << 1];
  iv[0] = iv[1] = 1;
  for (int i = 2; i < M; i++) iv[i] = mul(mod - mod / i, iv[mod % i]);
}
inline void dft(int *f, int lim) {
  for (int i = 0; i < lim; i++)
    if (i > rev[i]) swap(f[i], f[rev[i]]);
  for (int mid = 1, l = 1, a0, a1; mid < lim; mid <<= 1, l++)
    for (int i = 0; i < lim; i += mid << 1)
      for (int j = 0; j < mid; j++)
        a0 = f[i + j], a1 = mul(w[l][j], f[i + j + mid]),
        f[i + j] = add(a0, a1), f[i + j + mid] = dec(a0, a1);
}
inline void ntt(vector<int> &f, int lim, int kd) {
  dft(&f[0], lim);
  if (kd == -1) {
    reverse(f.begin() + 1, f.begin() + lim);
    for (int i = 0; i < lim; i++) Mul(f[i], iv[lim]);
  }
}
inline vector<int> operator+(vector<int> a, vector<int> b) {
  if (a.size() < b.size()) a.resize(b.size());
  for (int i = 0; i < b.size(); i++) Add(a[i], b[i]);
  return a;
}
inline vector<int> operator-(vector<int> a, vector<int> b) {
  if (a.size() < b.size()) a.resize(b.size());
  for (int i = 0; i < b.size(); i++) Dec(a[i], b[i]);
  return a;
}
inline vector<int> operator*(vector<int> a, int b) {
  for (int i = 0; i < a.size(); i++) Mul(a[i], b);
  return a;
}
inline vector<int> operator*(vector<int> a, vector<int> b) {
  if (!a.size() || !b.size()) return vector<int>(0);
  int deg = a.size() + b.size() - 1;
  if (a.size() <= 30 || b.size() <= 30) {
    vector<int> c(deg, 0);
    for (int i = 0; i < a.size(); i++)
      for (int j = 0; j < b.size(); j++) Add(c[i + j], mul(a[i], b[j]));
    return c;
  }
  int lim = 1;
  while (lim < deg) lim <<= 1;
  init_rev(lim);
  a.resize(lim), ntt(a, lim, 1);
  b.resize(lim), ntt(b, lim, 1);
  for (int i = 0; i < lim; i++) Mul(a[i], b[i]);
  ntt(a, lim, -1), a.resize(deg);
  return a;
}
inline vector<int> Inv(vector<int> a, int deg) {
  vector<int> b(1, ::Inv(a[0])), c;
  for (int lim = 4; lim < (deg << 2); lim <<= 1) {
    c.resize(lim >> 1);
    init_rev(lim);
    for (int i = 0; i < (lim >> 1); i++) c[i] = (i < a.size() ? a[i] : 0);
    c.resize(lim), ntt(c, lim, 1);
    b.resize(lim), ntt(b, lim, 1);
    for (int i = 0; i < lim; i++) Mul(b[i], dec(2, mul(b[i], c[i])));
    ntt(b, lim, -1), b.resize(lim >> 1);
  }
  b.resize(deg);
  return b;
}
inline vector<int> deriv(vector<int> a) {
  for (int i = 0; i + 1 < a.size(); i++) a[i] = mul(a[i + 1], i + 1);
  a.pop_back();
  return a;
}
inline vector<int> integ(vector<int> a) {
  a.push_back(0);
  for (int i = a.size() - 1; i; i--) a[i] = mul(a[i - 1], iv[i]);
  a[0] = 0;
  return a;
}
inline vector<int> Ln(vector<int> a, int deg) {
  a = integ(Inv(a, deg) * deriv(a)), a.resize(deg);
  return a;
}
inline vector<int> Exp(vector<int> a, int deg) {
  vector<int> b(1, 1), c;
  for (int lim = 2; lim < (deg << 1); lim <<= 1) {
    c = a - Ln(b, lim), Add(c[0], 1);
    b = b * c, b.resize(lim);
  }
  b.resize(deg);
  return b;
}
inline vector<int> ksm(vector<int> a, int b, int deg) {
  return Exp(Ln(a, deg) * b, deg);
}
inline vector<int> Mulx(vector<int> a) {
  a.push_back(0);
  for (int i = a.size() - 1; i; i--) a[i] = a[i - 1];
  a[0] = 0;
  return a;
}
inline vector<int> Divx(vector<int> a) {
  for (int i = 0; i + 1 < a.size(); i++) a[i] = a[i + 1];
  a.pop_back();
  return a;
}
}  // namespace Poly
using namespace Poly;
void write(vector<int> a) {
  for (int i = 0; i < a.size(); i++) cout << a[i] << " ";
  puts("");
}
inline vector<int> calc_g(int n) {
  int lm = n + 3;
  vector<int> f(lm);
  for (int i = 0; i < f.size(); i++) f[i] = ifac[i + 1];
  vector<int> res1 = Divx(Inv(Divx(vector<int>(1, 1) - f), lm) * f);
  res1.resize(lm);
  vector<int> t(2);
  t[0] = t[1] = 1, t = Inv(Divx(Ln(t, lm)), lm);
  vector<int> dn = Inv(Divx(vector<int>(1, 1) - t), lm), pt = ksm(t, n + 1, lm);
  vector<int> v1 = pt * dn, v2;
  v1.resize(lm), dn = dn * dn, dn.resize(lm);
  pt = pt * deriv(t), pt.resize(lm), v2 = pt * dn, v2.resize(lm);
  vector<int> res2(lm, 0);
  for (int i = 0; i < n; i++)
    res2[i] = mul(iv[n + 1], add(mul(n - i + 1, v1[i + 1]), v2[i + 1]));
  return res1 - res2;
}
int n;
int main() {
  init_w(), init_fac();
  n = read();
  vector<int> g = calc_g(n);
  for (int i = 0; i < g.size(); i++) Mul(g[i], fac[i]);
  g.resize(n);
  vector<int> f(n + 1);
  for (int i = 0; i <= n; i++) f[i] = (i & 1) ? dec(0, ifac[i]) : ifac[i];
  reverse(f.begin(), f.end());
  f = f * g;
  for (int i = 1; i <= n; i++)
    cout << mul(fac[n], mul(ifac[i - 1], f[n + i - 1])) << " ";
  return 0;
}