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;
std::vector<int> A, B;
int n, R[2000001], lim, ksm[30], L, w[2000001], t1[2000001], t2[2000001], m;
std::vector<int> val[1000001];
const int P = 998244353;
inline int read() {
  static int x;
  x = 0;
  static char ch;
  ch = getchar();
  while (ch < '0' || ch > '9') ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  return x;
}
inline void write(const int &x) {
  if (x > 9) write(x / 10);
  putchar((x % 10) + '0');
}
inline void print(std::vector<int> A, int n = -1) {
  if (!~n) n = A.size();
  for (int i = 0; i < n; i++) write(A[i]), putchar(' ');
  putchar('\n');
}
inline int mul(const int &a, const int &b) {
  return (long long)a * b - (long long)a * b / P * P;
}
inline int add(int a, const int &b) {
  a += b;
  return a >= P ? a - P : a;
}
inline int sub(int a, const int &b) {
  a -= b;
  return a < 0 ? a + P : a;
}
inline int qsm(int a, long long b = P - 2) {
  int ans = 1;
  while (b) {
    if (b & 1) ans = mul(ans, a);
    a = mul(a, a), b >>= 1;
  }
  return ans;
}
inline int inv(const int &a) {
  return (a <= 1) ? 1 : mul(P - P / a, inv(P % a));
}
inline int upp(int x) {
  while ((x & -x) != x) x += x & -x;
  return x;
}
inline void getRev(int x) {
  lim = upp(x);
  for (int i = 1; i < lim; i++)
    R[i] = (R[i >> 1] >> 1) | ((i & 1) ? (lim >> 1) : 0);
}
inline void NTT(int *A) {
  for (register int i = 0; i < lim; ++i)
    if (i < R[i]) swap(A[i], A[R[i]]);
  for (register int i = 1; i < lim; i <<= 1)
    for (register int j = 0; j < lim; j += (i << 1))
      for (register int k = 0, t = 1; k < i; ++k) {
        const int Ny = mul(A[i + j + k], w[i + k]);
        A[i + j + k] = sub(A[j + k], Ny);
        A[j + k] = add(A[j + k], Ny);
      }
}
inline void NTT_with_limit(int *A, const int &len) {
  for (register int i = 0; i < lim; ++i)
    if (i < R[i]) swap(A[i], A[R[i]]);
  static int half;
  half = lim >> 1;
  for (register int i = 1; i < half; i <<= 1) {
    for (register int j = 0; j < lim; j += (i << 1))
      for (register int k = 0; k < i; ++k) {
        const int Ny = mul(A[i + j + k], w[i + k]);
        A[i + j + k] = sub(A[j + k], Ny);
        A[j + k] = add(A[j + k], Ny);
      }
  }
  for (register int k = 0; k < len; ++k) {
    const int Ny = mul(A[half + k], w[half + k]);
    A[half + k] = sub(A[k], Ny);
    A[k] = add(A[k], Ny);
  }
}
inline std::vector<int> Res(std::vector<int> A, int x) {
  return A.resize(x), A;
}
inline std::vector<int> mul(std::vector<int> A, std::vector<int> B,
                            int len = -1) {
  if (~len) {
    if (A.size() > len) A.resize(len);
    if (B.size() > len) B.resize(len);
  }
  int size = A.size() + B.size() - 1;
  if (size <= 100) {
    std::vector<int> C(size);
    for (int i = 0; i < A.size(); ++i)
      for (int j = 0; j < B.size(); ++j)
        C[i + j] = add(C[i + j], mul(A[i], B[j]));
    if (~len) C.resize(len);
    return C;
  }
  getRev(size);
  memset(t1, 0, lim << 2);
  memset(t2, 0, lim << 2);
  for (int i = A.size() - 1; ~i; --i) t1[i] = A[i];
  for (int i = B.size() - 1; ~i; --i) t2[i] = B[i];
  NTT(t1);
  NTT(t2);
  for (int i = 0; i < lim; i++) t1[i] = mul(t1[i], t2[i]);
  std::reverse(t1 + 1, t1 + lim);
  if (~len) size = len;
  NTT_with_limit(t1, min(size, lim >> 1));
  lim = inv(lim);
  A.resize(0);
  for (int i = 0; i < size; i++) A.push_back(mul(t1[i], lim));
  return A;
}
inline int mul_inv(const int &a, const int &b) {
  return sub(add(b, b), mul(a, mul(b, b)));
}
inline std::vector<int> mul_inv(std::vector<int> A, const std::vector<int> &B,
                                int len = -1) {
  int size = A.size() + B.size() - 1;
  getRev(size);
  memset(t1, 0, lim << 2);
  memset(t2, 0, lim << 2);
  for (int i = A.size() - 1; ~i; --i) t1[i] = A[i];
  for (int i = B.size() - 1; ~i; --i) t2[i] = B[i];
  NTT(t1);
  NTT(t2);
  for (int i = 0; i < lim; i++)
    t1[i] = sub(add(t2[i], t2[i]), mul(t1[i], mul(t2[i], t2[i])));
  std::reverse(t1 + 1, t1 + lim);
  if (~len) size = len;
  NTT_with_limit(t1, min(size, lim >> 1));
  lim = inv(lim);
  A.resize(0);
  for (int i = 0; i < size; i++) A.push_back(mul(t1[i], lim));
  return A;
}
inline std::vector<int> inv(std::vector<int> A, int n) {
  A.resize(n);
  std::vector<int> B, t;
  B.push_back(inv(A[0]));
  static int last;
  last = 0;
  for (register int len = 2; (len >> 1) < n; len <<= 1) {
    for (; last < len; ++last) t.push_back(last < n ? A[last] : 0);
    B = mul_inv(t, B, len);
  }
  B.resize(n);
  return B;
}
inline std::vector<int> operator+(std::vector<int> A,
                                  const std::vector<int> &B) {
  if (A.size() < B.size()) A.resize(B.size());
  for (int i = 0; i < A.size(); ++i) A[i] = add(A[i], i < B.size() ? B[i] : 0);
  return A;
}
inline std::vector<int> operator-(std::vector<int> A,
                                  const std::vector<int> &B) {
  if (A.size() < B.size()) A.resize(B.size());
  for (int i = 0; i < A.size(); ++i) A[i] = sub(A[i], i < B.size() ? B[i] : 0);
  return A;
}
inline std::vector<int> operator/(std::vector<int> A, const int &n) {
  for (int i = 0; i < A.size(); ++i) A[i] = mul(A[i], inv(n));
  return A;
}
inline std::vector<int> operator-(const int &n, std::vector<int> B) {
  for (int i = 0; i < B.size(); ++i) B[i] = P - B[i];
  B[0] = add(B[0], n);
  return B;
}
inline std::vector<int> operator+(const int &n, std::vector<int> B) {
  B[0] = add(B[0], n);
  return B;
}
inline std::vector<int> operator*(const int &n, std::vector<int> A) {
  for (int i = 0; i < A.size(); ++i) A[i] = mul(n, A[i]);
  return A;
}
inline std::vector<int> diff(std::vector<int> A) {
  for (int i = 0; i < A.size() - 1; ++i) A[i] = mul(A[i + 1], i + 1);
  A[A.size() - 1] = 0;
  return A;
}
inline std::vector<int> inte(std::vector<int> A) {
  for (int i = A.size() - 1; i; --i) A[i] = mul(A[i - 1], inv(i));
  A[0] = 0;
  return A;
}
inline std::vector<int> ln(const std::vector<int> &A, const int &len) {
  return inte(mul(diff(A), inv(A, len), len));
}
inline std::vector<int> exp(const std::vector<int> &A, const int &n) {
  std::vector<int> B(1, 1);
  for (int i = 2; (i >> 1) < n; i <<= 1) B = mul(B, 1 - ln(B, i) + A, i);
  B.resize(n);
  return B;
}
int _inv[100020], _mul[100020];
int main() {
  n = read();
  for (int i = 1, wn; i < ((n + 10) << 2); i <<= 1) {
    wn = qsm(3, (P - 1) / (i << 1)), w[i] = 1;
    for (int j = 1; j < i; j++) w[i + j] = mul(w[i + j - 1], wn);
  }
  std::vector<int> t(n + 10);
  _inv[0] = _inv[1] = 1;
  for (int i = 2; i <= n + 10; i++) _inv[i] = mul(P - P / i, _inv[P % i]);
  for (int i = 1; i <= n + 10; i++)
    t[i - 1] = (i & 1) ? _inv[i] : (P - _inv[i]);
  t = inv(t, t.size());
  std::vector<int> g = ln(t, t.size());
  for (int i = 0; i < g.size(); i++) g[i] = mul(g[i], n + 1);
  g = exp(g, g.size());
  std::vector<int> Inv = t;
  for (int i = 1; i < Inv.size(); i++) Inv[i - 1] = P - Inv[i];
  Inv.pop_back();
  Inv = inv(Inv, Inv.size());
  g = mul(g, Inv);
  g.resize(n + 1);
  std::vector<int> h = diff(t);
  h = mul(h, g);
  h.resize(n + 1);
  h = mul(h, Inv);
  std::vector<int> ans(n);
  _mul[0] = _mul[1] = 1;
  for (int i = 2; i <= n; i++) _mul[i] = mul(i, _mul[i - 1]);
  for (int i = 0; i < n; i++)
    ans[i] = mul(_inv[n + 1], add(mul(n - i + 1, g[i + 1]), h[i + 1]));
  for (int i = 1; i <= n + 10; i++) _inv[i] = mul(_inv[i - 1], _inv[i]);
  std::vector<int> A(n + 10);
  for (int i = 2; i <= n + 10; i++) A[i - 2] = P - _inv[i];
  A = inv(A, A.size());
  std::vector<int> B(n + 5);
  for (int i = 1; i <= n + 5; i++) B[i - 1] = _inv[i];
  A = mul(A, B);
  for (int i = 0; i < n; i++) ans[i] = sub(A[i + 1], ans[i]);
  for (int i = 0; i < n; i++) ans[i] = mul(ans[i], _mul[i]);
  std::vector<int> l(n);
  for (int i = 0; i < n; i++) l[i] = (i & 1) ? P - _inv[i] : _inv[i];
  std::reverse(ans.begin(), ans.end());
  ans = mul(ans, l);
  ans.resize(n);
  std::reverse(ans.begin(), ans.end());
  for (int i = 0; i < n; i++) printf("%d ", mul(_mul[n], mul(ans[i], _inv[i])));
}