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 Mod = 998244353;
int add(int a, int b) { return a + b >= Mod ? a + b - Mod : a + b; }
int dec(int a, int b) { return a - b < 0 ? a - b + Mod : a - b; }
int mul(int a, int b) { return 1ll * a * b % Mod; }
int ksm(int a, int b) {
  int as = 1;
  for (; b; b >>= 1, a = mul(a, a))
    if (b & 1) as = mul(as, a);
  return as;
}
void Add(int &a, int b) { a = add(a, b); }
void Dec(int &a, int b) { a = dec(a, b); }
void Mul(int &a, int b) { a = mul(a, b); }
const int K = 18, N = 1 << K | 5;
int n, fc[N], ifc[N], iv[N];
int *w[K + 1], rv[N], bit, up;
void output(vector<int> a) {
  for (int i = 0; i < a.size(); i++) cout << a[i] << " ";
  puts("");
}
void fc_init(int n) {
  fc[0] = fc[1] = ifc[0] = ifc[1] = 1;
  for (int i = 2; i <= n; i++) fc[i] = mul(fc[i - 1], i);
  for (int i = 2; i <= n; i++) ifc[i] = mul(ifc[i - 1], iv[i]);
}
void NTT_init() {
  for (int i = 1; i <= K; i++) w[i] = new int[1 << (i - 1)];
  int wn = ksm(3, (Mod - 1) / (1 << K));
  w[K][0] = 1;
  for (int i = 1; i < (1 << (K - 1)); i++) w[K][i] = mul(w[K][i - 1], wn);
  for (int i = K - 1; i; i--)
    for (int j = 0; j < (1 << (i - 1)); j++) w[i][j] = w[i + 1][j << 1];
  iv[0] = iv[1] = 1;
  for (int i = 2; i <= (1 << K); i++) iv[i] = mul(Mod - Mod / i, iv[Mod % i]);
}
void init(int deg) {
  up = 1;
  bit = 0;
  while (up < deg) up <<= 1, ++bit;
  for (int i = 0; i < up; i++)
    rv[i] = (rv[i >> 1] >> 1) | ((i & 1) << (bit - 1));
}
vector<int> operator-(vector<int> a, vector<int> b) {
  if (a.size() < b.size()) a.resize(b.size());
  for (int i = 0; i < (int)b.size(); i++) Dec(a[i], b[i]);
  return a;
}
vector<int> divx(vector<int> a) {
  for (int i = 0; i < (int)a.size(); i++) a[i] = a[i + 1];
  return a.pop_back(), a;
}
void NTT(vector<int> &a, int typ = 1) {
  for (int i = 0; i < up; i++)
    if (i < rv[i]) swap(a[i], a[rv[i]]);
  for (int i = 1, l = 1; i < up; i <<= 1, ++l)
    for (int j = 0; j < up; j += (i << 1))
      for (int k = 0; k < i; k++) {
        int x = a[k + j], y = mul(w[l][k], a[k + j + i]);
        a[k + j] = add(x, y);
        a[k + j + i] = dec(x, y);
      }
  if (typ == -1) {
    reverse(a.begin() + 1, a.end());
    for (int i = 0, iv = ksm(up, Mod - 2); i < up; i++) Mul(a[i], iv);
  }
}
vector<int> operator*(vector<int> a, vector<int> b) {
  int dg = a.size() + b.size() - 1;
  if (a.size() <= 32 || b.size() <= 32) {
    vector<int> c(dg, 0);
    for (int i = 0; i < (int)a.size(); i++)
      for (int j = 0; j < (int)b.size(); j++) Add(c[i + j], mul(a[i], b[j]));
    return c;
  }
  init(dg);
  a.resize(up);
  b.resize(up);
  NTT(a);
  NTT(b);
  for (int i = 0; i < up; i++) Mul(a[i], b[i]);
  NTT(a, -1);
  a.resize(dg);
  return a;
}
vector<int> inv(vector<int> a, int deg) {
  vector<int> b(1, ksm(a[0], Mod - 2)), c;
  for (int lim = 2; (lim >> 1) < deg; lim <<= 1) {
    c.resize(lim);
    init(lim << 1);
    for (int i = 0; i < lim; i++) c[i] = i < (int)a.size() ? a[i] : 0;
    c.resize(up);
    b.resize(up);
    NTT(c);
    NTT(b);
    for (int i = 0; i < up; i++) Mul(b[i], dec(2, mul(b[i], c[i])));
    NTT(b, -1);
    b.resize(lim);
  }
  b.resize(deg);
  return b;
}
vector<int> deriv(vector<int> a) {
  for (int i = 0; i + 1 < (int)a.size(); i++) a[i] = mul(i + 1, a[i + 1]);
  a.pop_back();
  return a;
}
vector<int> integ(vector<int> a) {
  a.push_back(0);
  for (int i = a.size() - 1; i; i--) a[i] = mul(iv[i], a[i - 1]);
  a[0] = 0;
  return a;
}
vector<int> ln(vector<int> a, int dg) {
  if (dg == -1) dg = a.size();
  a = integ(deriv(a) * inv(a, dg));
  a.resize(dg);
  return a;
}
vector<int> Exp(vector<int> a, int dg) {
  if (dg == -1) dg = a.size();
  vector<int> b(1, 1), c;
  for (int lim = 2; lim < (dg << 1); lim <<= 1) {
    c = ln(b, lim);
    Dec(c[0], 1);
    for (int i = 0; i < lim; i++)
      c[i] = dec(i < (int)a.size() ? a[i] : 0, c[i]);
    b = b * c;
    b.resize(lim);
  }
  b.resize(dg);
  return b;
}
vector<int> polypw(vector<int> a, int k, int dg) {
  a = ln(a, dg);
  for (int i = 0; i < (int)a.size(); i++) Mul(a[i], k);
  return Exp(a, dg);
}
int main() {
  scanf("%d", &n);
  NTT_init();
  fc_init(n + 5);
  vector<int> phi(2, 1);
  phi = ln(phi, n + 3);
  phi = inv(divx(phi), n + 3);
  vector<int> t = vector<int>(1, 1) - phi;
  t = inv(divx(t), n + 3);
  vector<int> tt = t * t;
  tt.resize(n + 3);
  vector<int> mt = polypw(phi, n + 1, n + 3), dt = deriv(phi);
  t = mt * t;
  tt = mt * tt;
  t.resize(n + 3);
  tt.resize(n + 3);
  tt = tt * dt;
  tt.resize(n + 3);
  vector<int> em(n + 3, 0);
  for (int i = 0; i <= n + 2; i++) em[i] = ifc[i + 1];
  em = em * inv(divx(vector<int>(1, 1) - em), n + 3);
  vector<int> f(n + 1, 0);
  for (int i = 0, iv = ksm(n + 1, Mod - 2); i < n; i++) {
    f[i] = mul(iv, add(mul(t[i + 1], n - i + 1), tt[i + 1]));
    f[i] = dec(em[i + 1], f[i]);
    Mul(f[i], fc[i]);
  }
  vector<int> g(n, 0);
  for (int i = 0; i < n; i++) g[i] = (i & 1) ? dec(0, ifc[i]) : ifc[i];
  reverse(g.begin(), g.end());
  g = g * f;
  for (int i = 0; i < n; i++)
    cout << mul(ifc[i], mul(fc[n], g[i + n - 1])) << " ";
  return 0;
}