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;
const int I2 = 499122177;
namespace modular {
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; }
inline int Fast_Pow(int a, int b) {
  int res = 1;
  while (b) {
    if (b & 1) res = 1ll * res * a % Mod;
    a = 1ll * a * a % Mod;
    b >>= 1;
  }
  return res;
}
}  // namespace modular
using namespace modular;
namespace QR {
int w;
struct Data {
  int a, b;
  Data() { a = b = 0; }
  Data(int _a, int _b) {
    a = _a;
    b = _b;
  }
  friend Data operator*(Data t1, Data t2) {
    return Data((1ll * t1.a * t2.a + 1ll * t1.b * t2.b % Mod * w) % Mod,
                (1ll * t1.a * t2.b + 1ll * t1.b * t2.a) % Mod);
  }
};
int calc(int x) {
  if (!x) return x;
  int tmp = Fast_Pow(x, (Mod - 1) >> 1);
  if (tmp == Mod - 1) return -1;
  int a;
  while (true) {
    a = 1ll * rand() * rand() % Mod;
    w = ((1ll * a * a - x) % Mod + Mod) % Mod;
    if (Fast_Pow(w, (Mod - 1) >> 1) == Mod - 1) break;
  }
  Data res = Data(1, 0), H = Data(a, 1);
  tmp = (Mod + 1) >> 1;
  while (tmp) {
    if (tmp & 1) res = res * H;
    H = H * H;
    tmp >>= 1;
  }
  return min(res.a, Mod - res.a);
}
}  // namespace QR
namespace Poly {
int invv[24], len, bit, inv[1 << 20 | 5];
vector<int> rev[24], w[24];
inline void init_w(int lm = 1 << 18) {
  w[17].resize(1 << 17);
  w[17][0] = 1;
  w[17][1] = Fast_Pow(3, (Mod - 1) / lm);
  for (int i = 2; i < lm / 2; ++i)
    w[17][i] = 1ll * w[17][i - 1] * w[17][1] % Mod;
  for (int i = 16; i >= 0; --i) {
    w[i].resize(1 << i);
    for (int j = 0; j < (1 << i); ++j) w[i][j] = w[i + 1][j << 1];
  }
  inv[0] = inv[1] = 1;
  for (int i = 2; i <= lm; ++i)
    inv[i] = 1ll * (Mod - Mod / i) * inv[Mod % i] % Mod;
}
void init_r(int up) {
  len = 1;
  bit = 0;
  while (len < up) len <<= 1, bit++;
  if (invv[bit]) return;
  rev[bit].resize(len);
  for (int i = 0; i < len; ++i)
    rev[bit][i] = (rev[bit][i >> 1] >> 1) | ((i & 1) << (bit - 1));
  invv[bit] = Fast_Pow(len, Mod - 2);
}
inline vector<int> operator+(vector<int> a, vector<int> b) {
  int n = b.size();
  if (a.size() < n) a.resize(n);
  for (int i = 0; i < n; ++i) a[i] = add(a[i], b[i]);
  return a;
}
inline vector<int> poly_add(vector<int> a, vector<int> b) {
  int n = b.size();
  if (a.size() < n) a.resize(n);
  for (int i = 0; i < n; ++i) a[i] = add(a[i], b[i]);
  return a;
}
inline vector<int> operator-(vector<int> a, vector<int> b) {
  int n = b.size();
  if (a.size() < n) a.resize(n);
  for (int i = 0; i < n; ++i) a[i] = dec(a[i], b[i]);
  return a;
}
inline vector<int> poly_dec(vector<int> a, vector<int> b) {
  int n = b.size();
  if (a.size() < n) a.resize(n);
  for (int i = 0; i < n; ++i) a[i] = dec(a[i], b[i]);
  return a;
}
void NTT(vector<int> &A, int type) {
  for (int i = 0; i < len; ++i)
    if (i < rev[bit][i]) swap(A[i], A[rev[bit][i]]);
  for (int i = 1, t = 0; i < len; i <<= 1, ++t)
    for (int j = 0; j < len; j += i << 1)
      for (int k = 0; k < i; ++k) {
        int x = A[j + k];
        int y = 1ll * w[t][k] * A[j + k + i] % Mod;
        A[j + k] = add(x, y);
        A[j + k + i] = dec(x, y);
      }
  if (type == 1) return;
  reverse(++A.begin(), A.end());
  for (int i = 0; i < len; ++i) A[i] = 1ll * A[i] * invv[bit] % Mod;
}
vector<int> operator*(vector<int> a, vector<int> b) {
  int n = a.size(), m = b.size(), t = n + m - 1;
  if (n <= 30 || m <= 30) {
    vector<int> c(t);
    for (int i = 0; i < n; ++i)
      if (a[i])
        for (int j = 0; j < m; ++j)
          c[i + j] = (c[i + j] + 1ll * a[i] * b[j]) % Mod;
    return c;
  }
  init_r(t);
  a.resize(len);
  NTT(a, 1);
  b.resize(len);
  NTT(b, 1);
  for (int i = 0; i < len; ++i) a[i] = 1ll * a[i] * b[i] % Mod;
  return NTT(a, -1), a.resize(t), a;
}
vector<int> poly_mul(vector<int> a, vector<int> b) {
  int n = a.size(), m = b.size(), t = n + m - 1;
  if (n <= 30 || m <= 30) {
    vector<int> c(t);
    for (int i = 0; i < n; ++i)
      if (a[i])
        for (int j = 0; j < m; ++j)
          c[i + j] = (c[i + j] + 1ll * a[i] * b[j]) % Mod;
    return c;
  }
  init_r(t);
  a.resize(len);
  NTT(a, 1);
  b.resize(len);
  NTT(b, 1);
  for (int i = 0; i < len; ++i) a[i] = 1ll * a[i] * b[i] % Mod;
  return NTT(a, -1), a.resize(t), a;
}
vector<int> poly_inv(vector<int> a, int K) {
  vector<int> b(1, Fast_Pow(a[0], Mod - 2)), c;
  for (int i = 1, l = 2, n = a.size(); i < K; i <<= 1, l <<= 1) {
    init_r(l << 1);
    c.resize(l);
    for (int j = 0; j < l; ++j) c[j] = j < n ? a[j] : 0;
    c.resize(len);
    NTT(c, 1);
    b.resize(len);
    NTT(b, 1);
    for (int j = 0; j < len; ++j)
      b[j] = 1ll * b[j] * (2 - 1ll * b[j] * c[j] % Mod + Mod) % Mod;
    NTT(b, -1);
    b.resize(l);
  }
  return b.resize(K), b;
}
vector<int> poly_sqrt(vector<int> a, int K) {
  vector<int> b(1, QR::calc(a[0])), c, binv;
  for (int i = 1, l = 2, n = a.size(); i < K; i <<= 1, l <<= 1) {
    binv = poly_inv(b, l);
    c.resize(l);
    for (int j = 0; j < l; ++j) c[j] = j < n ? a[j] : 0;
    c = c * binv;
    c.resize(l);
    b.resize(l);
    for (int j = 0; j < l; ++j) b[j] = 1ll * inv[2] * (c[j] + b[j]) % Mod;
  }
  return b.resize(K), b;
}
vector<int> poly_deriv(vector<int> a) {
  int n = a.size();
  for (int i = 1; i < n; ++i) a[i - 1] = 1ll * a[i] * i % Mod;
  a.pop_back();
  return a;
}
vector<int> poly_integ(vector<int> a) {
  int n = a.size();
  a.push_back(0);
  for (int i = n - 1; i >= 0; --i) a[i + 1] = 1ll * a[i] * inv[i + 1] % Mod;
  a[0] = 0;
  return a;
}
vector<int> poly_ln(vector<int> a, int K) {
  a = poly_deriv(a) * poly_inv(a, K);
  a.resize(K - 1);
  return poly_integ(a);
}
vector<int> poly_exp(vector<int> a, int K) {
  vector<int> b(1, 1), c;
  for (int i = 1, l = 2, n = a.size(); i < K; i <<= 1, l <<= 1) {
    c.resize(l);
    for (int j = 0; j < l; ++j) c[j] = j < n ? a[j] : 0;
    c[0] = add(c[0], 1);
    b = b * (c - poly_ln(b, l));
    b.resize(l);
  }
  return b.resize(K), b;
}
const int B = 32;
const int Bbit = 5;
int F[1 << 20 | 5], A[1 << 20 | 5], L, tim = 0;
vector<int> BitF[23][B], tmp;
vector<int> H[23][B];
void cdq(int l, int r) {
  if (r - l + 1 <= 64) {
    for (int i = l; i <= r; ++i) {
      A[i] = 1ll * A[i] * inv[i] % Mod;
      for (int j = 1; j <= r - i; ++j)
        A[i + j] = (A[i + j] + 1ll * A[i] * F[j]) % Mod;
    }
    return;
  }
  int lenB = (r - l + 1) / B;
  int gg = 0;
  while ((1 << gg) < lenB) gg++;
  for (int i = 1; i < B; ++i) {
    H[gg][i].resize(lenB << 1);
    for (int j = 0; j < lenB * 2; ++j) H[gg][i][j] = 0;
  }
  for (int i = 0; i < B; ++i) {
    if (i) {
      init_r(lenB << 1);
      NTT(H[gg][i], -1);
      for (int j = 0; j < lenB; ++j)
        A[l + i * lenB + j] = add(A[l + i * lenB + j], H[gg][i][j + lenB]);
    }
    cdq(l + i * lenB, l + (i + 1) * lenB - 1);
    tmp.resize(lenB << 1);
    for (int j = 0; j < lenB; ++j) tmp[j] = A[l + i * lenB + j];
    for (int j = lenB; j < lenB * 2; ++j) tmp[j] = 0;
    init_r(lenB << 1);
    NTT(tmp, 1);
    for (int j = i + 1; j < B; ++j) {
      for (int k = 0; k < lenB * 2; ++k)
        H[gg][j][k] =
            (H[gg][j][k] + 1ll * BitF[bit - 1][j - i - 1][k] * tmp[k]) % Mod;
    }
  }
}
vector<int> Poly_exp(vector<int> a, int K) {
  if (a.size() == 1) {
    vector<int> c(K);
    c[0] = 1;
    return c;
  }
  L = 1;
  tim = 0;
  while (L < K) L <<= 1, tim++;
  if (a.size() < L) a.resize(L);
  F[0] = 0;
  for (int i = 1; i <= L - 1; ++i) F[i] = 1ll * a[i] * i % Mod;
  int at = L, z = tim;
  while (z >= Bbit) {
    at /= B;
    z -= Bbit;
    for (int i = 0; i < B - 1; ++i) {
      BitF[z][i].resize(at * 2);
      for (int j = 0; j < at * 2; ++j) BitF[z][i][j] = F[i * at + j];
      init_r(at * 2);
      NTT(BitF[z][i], 1);
    }
  }
  A[0] = 1;
  for (int i = 1; i <= L - 1; ++i) A[i] = 0;
  cdq(0, L - 1);
  vector<int> c(K);
  for (int i = 0; i < K; ++i) c[i] = A[i];
  return c;
}
vector<int> Div(vector<int> a, vector<int> b) {
  int n = a.size() - 1, m = b.size() - 1;
  reverse(a.begin(), a.end());
  reverse(b.begin(), b.end());
  b = poly_inv(b, n - m + 1);
  a = a * b;
  a.resize(n - m + 1);
  reverse(a.begin(), a.end());
  return a;
}
vector<int> Left(vector<int> a) {
  for (int i = 0; i < a.size() - 1; ++i) a[i] = a[i + 1];
  a.pop_back();
  return a;
}
vector<int> Right(vector<int> a) {
  int t = a.size();
  a.resize(t + 1);
  for (int i = a.size() - 2; i >= 0; --i) a[i + 1] = a[i];
  a[0] = 0;
  return a;
}
vector<int> poly_pow(vector<int> a, int K, int m) {
  int t = a[0], invt = Fast_Pow(t, Mod - 2), ft = Fast_Pow(t, m);
  for (int i = 0; i < a.size(); ++i) a[i] = 1ll * a[i] * invt % Mod;
  vector<int> b = poly_ln(a, K);
  for (int i = 0; i < K; ++i) b[i] = 1ll * b[i] * m % Mod;
  b = Poly_exp(b, K);
  for (int i = 0; i < K; ++i) b[i] = 1ll * b[i] * ft % Mod;
  return b;
}
}  // namespace Poly
int n;
int fact[100010], ifac[100010], inv[100010];
void init(int N) {
  fact[0] = 1;
  for (int i = (1); i <= (N); ++i) fact[i] = mul(fact[i - 1], i);
  inv[0] = inv[1] = 1;
  for (int i = (2); i <= (N); ++i) inv[i] = mul(Mod - Mod / i, inv[Mod % i]);
  ifac[0] = 1;
  for (int i = (1); i <= (N); ++i) ifac[i] = mul(ifac[i - 1], inv[i]);
}
vector<int> H, Hn, H1, H2, H3, F;
int ym[100010], R[100010];
vector<int> RK, DEC, Ans;
int main() {
  scanf("%d", &n);
  Poly::init_w();
  init(n + 5);
  H.resize(n + 6);
  H[0] = 1;
  H[1] = 1;
  H = Poly::poly_ln(H, n + 6);
  for (int i = 0; i < H.size() - 1; ++i) H[i] = H[i + 1];
  H.pop_back();
  H = Poly::poly_inv(H, n + 5);
  Hn = Poly::poly_ln(H, n + 5);
  for (int i = (0); i <= (n + 4); ++i) Hn[i] = mul(Hn[i], n + 1);
  Hn = Poly::Poly_exp(Hn, n + 5);
  H1.resize(n + 5);
  for (int i = (1); i <= (n + 4); ++i) H1[i] = dec(0, H[i]);
  for (int i = (0); i <= (n + 3); ++i) H1[i] = H1[i + 1];
  H1.pop_back();
  H1 = Poly::poly_inv(H1, n + 4);
  H2 = Poly::poly_mul(H1, H1);
  H2.resize(n + 4);
  H1 = Poly::poly_mul(H1, Hn);
  H1.resize(n + 4);
  H3 = Poly::poly_mul(Poly::poly_deriv(H), Hn);
  H3.resize(n + 4);
  H2 = Poly::poly_mul(H2, H3);
  H2.resize(n + 4);
  for (int m = (0); m <= (n + 1); ++m)
    ym[m] = mul(add(mul(m, H1[n - m + 2]), H2[n - m + 2]), inv[n + 1]);
  for (int k = (0); k <= (n - 1); ++k) R[k] = dec(0, ym[n + 1 - k]);
  F.resize(n + 4);
  for (int i = (0); i <= (n + 3); ++i) F[i] = ifac[i + 1];
  for (int i = (0); i <= (n + 2); ++i) F[i] = dec(0, F[i + 1]);
  F.pop_back();
  F = Poly::poly_inv(F, n + 3);
  for (int k = (0); k <= (n - 1); ++k) {
    R[k] = add(R[k], F[k + 1]);
    R[k] = mul(R[k], fact[k]);
  }
  R[0] = dec(R[0], 1);
  RK.resize(n + 1);
  for (int k = (0); k <= (n); ++k) RK[k] = R[k];
  DEC.resize(n + 1);
  for (int i = (0); i <= (n); ++i)
    if (i & 1)
      DEC[n - i] = dec(0, ifac[i]);
    else
      DEC[n - i] = ifac[i];
  Ans = Poly::poly_mul(RK, DEC);
  for (int k = (0); k <= (n - 1); ++k)
    printf("%d ", mul(mul(fact[n], ifac[k]), Ans[n + k]));
  return 0;
}