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 FFTN = 1 << 19;
int power(int x, int y) {
  int s = 1;
  for (; y; y /= 2, x = 1ll * x * x % MOD)
    if (y & 1) s = 1ll * s * x % MOD;
  return s;
}
namespace FFT {
int w[FFTN + 5], W[FFTN + 5], R[FFTN + 5];
void FFTinit() {
  W[0] = 1;
  W[1] = power(3, (MOD - 1) / FFTN);
  for (int i = (int)(2); i <= (int)(FFTN); i++)
    W[i] = 1ll * W[i - 1] * W[1] % MOD;
}
int FFTinit(int n) {
  int L = 1;
  for (; L <= n; L <<= 1)
    ;
  for (int i = (int)(0); i <= (int)(L - 1); i++)
    R[i] = (R[i >> 1] >> 1) | ((i & 1) ? (L >> 1) : 0);
  return L;
}
int A[FFTN + 5], B[FFTN + 5];
unsigned long long p[FFTN + 5];
void DFT(int *a, int n) {
  for (int i = (int)(0); i <= (int)(n - 1); i++) p[R[i]] = a[i];
  for (int d = 1; d < n; d <<= 1) {
    int len = FFTN / (d << 1);
    for (int i = 0, j = 0; i < d; i++, j += len) w[i] = W[j];
    for (int i = 0; i < n; i += (d << 1))
      for (int j = 0; j < d; j++) {
        int y = p[i + j + d] * w[j] % MOD;
        p[i + j + d] = p[i + j] + MOD - y;
        p[i + j] += y;
      }
    if (d == 1 << 15)
      for (int i = (int)(0); i <= (int)(n - 1); i++) p[i] %= MOD;
  }
  for (int i = (int)(0); i <= (int)(n - 1); i++) a[i] = p[i] % MOD;
}
void IDFT(int *a, int n) {
  for (int i = (int)(0); i <= (int)(n - 1); i++) p[R[i]] = a[i];
  for (int d = 1; d < n; d <<= 1) {
    int len = FFTN / (d << 1);
    for (int i = 0, j = FFTN; i < d; i++, j -= len) w[i] = W[j];
    for (int i = 0; i < n; i += (d << 1))
      for (int j = 0; j < d; j++) {
        int y = p[i + j + d] * w[j] % MOD;
        p[i + j + d] = p[i + j] + MOD - y;
        p[i + j] += y;
      }
    if (d == 1 << 15)
      for (int i = (int)(0); i <= (int)(n - 1); i++) p[i] %= MOD;
  }
  int val = power(n, MOD - 2);
  for (int i = (int)(0); i <= (int)(n - 1); i++) a[i] = p[i] * val % MOD;
}
vector<int> Norm(vector<int> a) {
  for (; a.size() && !a.back(); a.pop_back())
    ;
  return a;
}
vector<int> Plus(const vector<int> &a, const vector<int> &b) {
  int sza = a.size() - 1, szb = b.size() - 1;
  vector<int> ans(max(sza, szb) + 1);
  for (int i = (int)(0); i <= (int)(sza); i++) ans[i] = a[i];
  for (int i = (int)(0); i <= (int)(szb); i++) ans[i] = (ans[i] + b[i]) % MOD;
  return ans;
}
vector<int> Minus(const vector<int> &a, const vector<int> &b) {
  int sza = a.size() - 1, szb = b.size() - 1;
  vector<int> ans(max(sza, szb) + 1);
  for (int i = (int)(0); i <= (int)(sza); i++) ans[i] = a[i];
  for (int i = (int)(0); i <= (int)(szb); i++)
    ans[i] = (ans[i] + MOD - b[i]) % MOD;
  return ans;
}
vector<int> Mul(const vector<int> &a, const vector<int> &b) {
  int sza = a.size() - 1, szb = b.size() - 1;
  vector<int> ans(sza + szb + 1);
  if (sza <= 30 || szb <= 30) {
    for (int i = (int)(0); i <= (int)(sza); i++)
      for (int j = (int)(0); j <= (int)(szb); j++)
        ans[i + j] = (ans[i + j] + 1ll * a[i] * b[j]) % MOD;
    return ans;
  }
  int L = FFTinit(sza + szb);
  for (int i = (int)(0); i <= (int)(L - 1); i++) A[i] = (i <= sza ? a[i] : 0);
  for (int i = (int)(0); i <= (int)(L - 1); i++) B[i] = (i <= szb ? b[i] : 0);
  DFT(A, L);
  DFT(B, L);
  for (int i = (int)(0); i <= (int)(L - 1); i++) A[i] = 1ll * A[i] * B[i] % MOD;
  IDFT(A, L);
  for (int i = (int)(0); i <= (int)(sza + szb); i++) ans[i] = A[i];
  return ans;
}
void Getinv(int *a, int *b, int n) {
  if (n == 1) {
    b[0] = power(a[0], MOD - 2);
    return;
  }
  int nn = (n + 1) / 2;
  Getinv(a, b, nn);
  int L = FFTinit(2 * n);
  for (int i = (int)(0); i <= (int)(L - 1); i++) A[i] = (i < n ? a[i] : 0);
  for (int i = (int)(0); i <= (int)(L - 1); i++) B[i] = (i < nn ? b[i] : 0);
  DFT(A, L);
  DFT(B, L);
  for (int i = (int)(0); i <= (int)(L - 1); i++)
    A[i] = 1ll * B[i] * (2 + MOD - 1ll * A[i] * B[i] % MOD) % MOD;
  IDFT(A, L);
  for (int i = (int)(0); i <= (int)(n - 1); i++) b[i] = A[i];
}
vector<int> getinv(vector<int> a, int n) {
  int *b = new int[n];
  int *c = new int[n];
  int sz = a.size();
  for (int i = (int)(0); i <= (int)(n - 1); i++) b[i] = (i < sz ? a[i] : 0);
  for (int i = (int)(0); i <= (int)(n - 1); i++) c[i] = 0;
  vector<int> ans(n);
  Getinv(b, c, n);
  for (int i = (int)(0); i <= (int)(n - 1); i++) ans[i] = c[i];
  delete[] b;
  delete[] c;
  return ans;
}
vector<int> divide(vector<int> a, vector<int> b) {
  int sza = a.size(), szb = b.size();
  if (sza < szb) return vector<int>(0);
  vector<int> b0 = b, a0 = a;
  reverse(b0.begin(), b0.end());
  reverse(a0.begin(), a0.end());
  b0 = Mul(getinv(b0, sza - szb + 1), a0);
  b0.resize(sza - szb + 1);
  reverse(b0.begin(), b0.end());
  return b0;
}
vector<int> MODdulo(vector<int> a, vector<int> b) {
  vector<int> ans = Minus(a, Mul(divide(a, b), b));
  ans.resize(b.size() - 1);
  return ans;
}
int Cipolla(int x) {
  int a = 1;
  for (;; ++a)
    if (power((1ll * a * a + MOD - x) % MOD, (MOD - 1) / 2) == MOD - 1) break;
  int w = (1ll * a * a + MOD - x) % MOD, T = (MOD + 1) / 2;
  pair<int, int> v1(1, 0), v2(a, 1);
  for (; T;) {
    if (T & 1) {
      int val1 =
          (1ll * v1.first * v2.first + 1ll * w * v1.second % MOD * v2.second) %
          MOD;
      int val2 =
          (1ll * v1.first * v2.second + 1ll * v1.second * v2.first) % MOD;
      v1 = pair<int, int>(val1, val2);
    }
    if (T /= 2) {
      int val1 =
          (1ll * v2.first * v2.first + 1ll * w * v2.second % MOD * v2.second) %
          MOD;
      int val2 =
          (1ll * v2.first * v2.second + 1ll * v2.second * v2.first) % MOD;
      v2 = pair<int, int>(val1, val2);
    }
  }
  return v1.first;
}
void Getsqrt(int *a, int *b, int n) {
  if (n == 1) {
    b[0] = Cipolla(a[0]);
    if (b[0] > MOD - b[0]) b[0] = MOD - b[0];
    return;
  }
  int nn = (n + 1) / 2;
  Getsqrt(a, b, nn);
  int *c = new int[n];
  for (int i = (int)(0); i <= (int)(n - 1); i++) c[i] = 0;
  Getinv(b, c, n);
  int L = FFTinit(2 * n);
  for (int i = (int)(0); i <= (int)(L - 1); i++) A[i] = (i < n ? a[i] : 0);
  for (int i = (int)(0); i <= (int)(L - 1); i++) B[i] = (i < n ? c[i] : 0);
  DFT(A, L);
  DFT(B, L);
  for (int i = (int)(0); i <= (int)(L - 1); i++) A[i] = 1ll * A[i] * B[i] % MOD;
  IDFT(A, L);
  for (int i = (int)(0); i <= (int)(n - 1); i++)
    b[i] = 1ll * (b[i] + A[i]) * (MOD + 1) / 2 % MOD;
  delete[] c;
}
vector<int> getsqrt(vector<int> a, int n) {
  int *b = new int[n];
  int *c = new int[n];
  int sz = a.size();
  for (int i = (int)(0); i <= (int)(n - 1); i++) b[i] = (i < sz ? a[i] : 0);
  for (int i = (int)(0); i <= (int)(n - 1); i++) c[i] = 0;
  vector<int> ans(n);
  Getsqrt(b, c, n);
  for (int i = (int)(0); i <= (int)(n - 1); i++) ans[i] = c[i];
  delete[] b;
  delete[] c;
  return ans;
}
vector<int> Int(vector<int> a) {
  int sza = a.size() - 1;
  vector<int> ans(sza + 2);
  ans[0] = 0;
  for (int i = (int)(1); i <= (int)(sza + 1); i++)
    ans[i] = 1ll * a[i - 1] * power(i, MOD - 2) % MOD;
  return ans;
}
vector<int> Prime(vector<int> a) {
  int sza = a.size() - 1;
  vector<int> ans(sza);
  for (int i = (int)(1); i <= (int)(sza); i++)
    ans[i - 1] = 1ll * a[i] * i % MOD;
  return ans;
}
vector<int> getLn(vector<int> a, int n) {
  assert(a[0] == 1);
  if ((int)a.size() > n) a.resize(n);
  vector<int> res = Int(Mul(Prime(a), getinv(a, n)));
  res.resize(n);
  return res;
}
void Getexp(unsigned long long *a, unsigned long long *b, int l, int r) {
  if (r - l + 1 <= 64) {
    for (int i = (int)(l); i <= (int)(r); i++) b[i] %= MOD;
    for (int i = (int)(l); i <= (int)(r); i++) {
      if (i == 0)
        b[i] = 1;
      else
        b[i] = b[i] % MOD * power(i, MOD - 2) % MOD;
      for (int j = (int)(1); j <= (int)(r - i); j++) b[i + j] += b[i] * a[j];
      if ((i & 15) == 15)
        for (int j = (int)(i); j <= (int)(r); j++) b[j] %= MOD;
    }
    return;
  }
  int len = (r - l + 1) / 16;
  unsigned long long *c[16], *d[16];
  int L = FFTinit(2 * len - 1);
  int *arr = new int[L];
  for (int i = (int)(0); i <= (int)(15); i++) {
    d[i] = new unsigned long long[L];
    for (int j = (int)(0); j <= (int)(L - 1); j++) d[i][j] = 0;
  }
  for (int i = (int)(0); i <= (int)(14); i++) {
    c[i] = new unsigned long long[L];
    for (int j = (int)(0); j <= (int)(L - 1); j++) arr[j] = a[i * len + j];
    DFT(arr, L);
    for (int j = (int)(0); j <= (int)(L - 1); j++) c[i][j] = arr[j];
  }
  for (int i = (int)(0); i <= (int)(15); i++) {
    if (i != 0) {
      for (int j = (int)(0); j <= (int)(L - 1); j++) arr[j] = d[i][j] % MOD;
      IDFT(arr, L);
      for (int j = (int)(0); j <= (int)(len - 1); j++)
        b[l + i * len + j] += arr[len + j];
    }
    Getexp(a, b, l + i * len, l + i * len + len - 1);
    if (i != 15) {
      L = FFTinit(2 * len - 1);
      for (int j = (int)(0); j <= (int)(L - 1); j++)
        arr[j] = (j < len ? b[l + i * len + j] : 0);
      DFT(arr, L);
      for (int j = (int)(0); j <= (int)(14 - i); j++)
        for (int k = (int)(0); k <= (int)(L - 1); k++)
          d[i + j + 1][k] += arr[k] * c[j][k];
    }
  }
  delete[] arr;
  for (int i = (int)(0); i <= (int)(14); i++) delete[] c[i];
  for (int i = (int)(0); i <= (int)(15); i++) delete[] d[i];
}
vector<int> getexp(vector<int> a, int n) {
  int m = 1, sza = a.size();
  for (; m <= n; m <<= 1)
    ;
  unsigned long long *b = new unsigned long long[m],
                     *c = new unsigned long long[m];
  for (int i = (int)(0); i <= (int)(m - 1); i++)
    b[i] = (i < sza ? 1ll * i * a[i] % MOD : 0);
  for (int i = (int)(0); i <= (int)(m - 1); i++) c[i] = 0;
  Getexp(b, c, 0, m - 1);
  vector<int> ans(n);
  for (int i = (int)(0); i <= (int)(n - 1); i++) ans[i] = c[i];
  delete[] b;
  delete[] c;
  return ans;
}
vector<int> read() {
  int n;
  scanf("%d", &n);
  vector<int> ans(n);
  for (int i = (int)(0); i <= (int)(n - 1); i++) scanf("%d", &ans[i]);
  return ans;
}
vector<int> read(int n) {
  vector<int> ans(n);
  for (int i = (int)(0); i <= (int)(n - 1); i++) scanf("%d", &ans[i]);
  return ans;
}
void write(const vector<int> &a) {
  for (auto i : a) printf("%d ", i);
}
void writeln(const vector<int> &a) {
  for (auto i : a) printf("%d ", i);
  puts("");
}
}  // namespace FFT
using FFT::getexp;
using FFT::getinv;
using FFT::getLn;
using FFT::Minus;
using FFT::Mul;
using FFT::Prime;
using FFT::writeln;
const int N = FFTN;
int fac[N], inv[N], Inv[N];
int f[N], n;
void init() {
  fac[0] = inv[0] = 1;
  for (int i = (int)(1); i <= (int)(N - 1); i++) {
    fac[i] = 1ll * fac[i - 1] * i % MOD;
    inv[i] = power(fac[i], MOD - 2);
    Inv[i] = power(i, MOD - 2);
  }
}
int C(int x, int y) {
  if (x < 0 || y < 0 || y > x) return 0;
  return 1ll * fac[x] * inv[y] % MOD * inv[x - y] % MOD;
}
vector<int> power(vector<int> a, int b) {
  assert(a[0] == 1);
  a = getLn(a, n + 2);
  for (auto &i : a) i = 1ll * i * b % MOD;
  return getexp(a, n + 2);
}
int main() {
  init();
  FFT::FFTinit();
  scanf("%d", &n);
  vector<int> H(n + 2), IH(n + 2), G(n + 2), Phi(n + 2);
  for (int i = (int)(0); i <= (int)(n + 1); i++) {
    G[i] = inv[i + 1];
    Phi[i] = 1ll * (i & 1 ? MOD - 1 : 1) * Inv[i + 1] % MOD;
  }
  for (int i = (int)(1); i <= (int)(n + 1); i++) {
    H[i] = inv[i];
    IH[i] = 1ll * (i & 1 ? 1 : MOD - 1) * Inv[i] % MOD;
  }
  Phi = getinv(Phi, n + 2);
  vector<int> F1 = power(Phi, n + 1);
  vector<int> tmp(n + 1);
  for (int i = (int)(0); i <= (int)(n); i++) tmp[i] = MOD - Phi[i + 1];
  vector<int> F2 = getinv(tmp, n + 2);
  vector<int> val1 = Mul(F1, F2);
  vector<int> val2 = Mul(F1, Mul(Prime(Phi), Mul(F2, F2)));
  for (int i = (int)(0); i <= (int)(n); i++) tmp[i] = MOD - G[i + 1];
  vector<int> val3 = getinv(tmp, n + 2);
  for (int i = (int)(0); i <= (int)(n); i++) {
    f[i] = (1ll * (n - i + 1) * val1[i + 1] + val2[i + 1]) % MOD;
    f[i] = (val3[i + 1] + MOD - 1ll * f[i] * power(n + 1, MOD - 2) % MOD) % MOD;
  }
  f[0] = (f[0] + MOD - 1) % MOD;
  vector<int> res1(n + 1), res2(n + 1);
  for (int i = (int)(1); i <= (int)(n); i++)
    res1[i] = 1ll * f[i - 1] * fac[i - 1] % MOD;
  for (int i = (int)(0); i <= (int)(n); i++)
    res2[n - i] = 1ll * (i & 1 ? MOD - 1 : 1) * inv[i] % MOD;
  vector<int> res = Mul(res1, res2);
  for (int i = (int)(1); i <= (int)(n); i++)
    printf("%d ", int(1ll * res[i + n] * fac[n] % MOD * inv[i - 1] % MOD));
}