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;
long long qpow(long long x, long long y = 998244353 - 2) {
  long long r = 1;
  for (; y; y >>= 1, x = x * x % 998244353)
    if (y & 1) r = r * x % 998244353;
  return r;
}
int n;
int g[(262144 + 10)], ans[(262144 + 10)];
long long fac[(262144 + 10)], ifac[(262144 + 10)], inv[(262144 + 10)];
void initC(int n) {
  fac[0] = 1;
  for (int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % 998244353;
  ifac[n] = qpow(fac[n]);
  for (int i = n - 1; i >= 0; --i) ifac[i] = ifac[i + 1] * (i + 1) % 998244353;
  for (int i = 1; i <= n; ++i) inv[i] = ifac[i] * fac[i - 1] % 998244353;
}
long long C(int m, int n) {
  return fac[m] * ifac[n] % 998244353 * ifac[m - n] % 998244353;
}
int re[(262144 + 10)], nN;
void setlen(int n) {
  int bit = 0;
  for (nN = 1; nN <= n; nN <<= 1, ++bit)
    ;
  for (int i = 1; i < nN; ++i) re[i] = re[i >> 1] >> 1 | (i & 1) << bit - 1;
}
void dft(int A[], int flag) {
  for (int i = 0; i < nN; ++i)
    if (i < re[i]) swap(A[i], A[re[i]]);
  static int wnk[(262144 + 10)];
  for (int i = 1; i < nN; i <<= 1) {
    long long wn =
        qpow(3, flag == 1 ? (998244353 - 1) / (2 * i)
                          : 998244353 - 1 - (998244353 - 1) / (2 * i));
    wnk[0] = 1;
    for (int k = 1; k < i; ++k) wnk[k] = wnk[k - 1] * wn % 998244353;
    for (int j = 0; j < nN; j += i << 1)
      for (int k = 0; k < i; ++k) {
        long long x = A[j + k], y = (long long)A[j + k + i] * wnk[k];
        A[j + k] = (x + y) % 998244353;
        A[j + k + i] = (x - y) % 998244353;
      }
  }
  for (int i = 0; i < nN; ++i) A[i] = (A[i] + 998244353) % 998244353;
  if (flag == -1) {
    long long invn = qpow(nN);
    for (int i = 0; i < nN; ++i) A[i] = A[i] * invn % 998244353;
  }
}
void clear(int A[], int siz = nN) { memset(A, 0, sizeof(int) * siz); }
void multi(int c[], int a[], int b[], int n) {
  static int A[(262144 + 10)], B[(262144 + 10)];
  setlen(n * 2);
  clear(A), clear(B);
  memcpy(A, a, sizeof(int) * (n + 1));
  memcpy(B, b, sizeof(int) * (n + 1));
  dft(A, 1), dft(B, 1);
  for (int i = 0; i < nN; ++i) A[i] = (long long)A[i] * B[i] % 998244353;
  dft(A, -1);
  for (int i = 0; i <= n * 2; ++i) c[i] = A[i];
}
void getinv(int c[], int a[], int n) {
  static int b[(262144 + 10)], A[(262144 + 10)], B[(262144 + 10)];
  int nn = 1;
  for (; nn < n; nn <<= 1)
    ;
  clear(b, nn);
  b[0] = qpow(a[0]);
  for (int i = 1; i < n; i <<= 1) {
    setlen(i * 3 - 1);
    clear(A), clear(B);
    memcpy(A, a, sizeof(int) * min(n, i * 2));
    memcpy(B, b, sizeof(int) * i);
    dft(A, 1), dft(B, 1);
    for (int j = 0; j < nN; ++j)
      B[j] = (long long)B[j] * B[j] % 998244353 * A[j] % 998244353;
    dft(B, -1);
    for (int j = 0; j < i * 2; ++j)
      b[j] = (2ll * b[j] - B[j] + 998244353) % 998244353;
  }
  memcpy(c, b, sizeof(int) * n);
}
void getpow(int c[], int a[], int n, int idx) {
  static int p[(262144 + 10)], q[(262144 + 10)];
  memcpy(p, a, sizeof(int) * n);
  memset(q, 0, sizeof(int) * n);
  q[0] = 1;
  setlen((n - 1) * 2);
  while (idx) {
    dft(p, 1);
    if (idx & 1) {
      dft(q, 1);
      for (int i = 0; i < nN; ++i) q[i] = (long long)q[i] * p[i] % 998244353;
      dft(q, -1);
      memset(q + n, 0, sizeof(int) * (nN - n));
    }
    if (idx >>= 1) {
      for (int i = 0; i < nN; ++i) p[i] = (long long)p[i] * p[i] % 998244353;
      dft(p, -1);
      memset(p + n, 0, sizeof(int) * (nN - n));
    } else
      break;
  }
  memcpy(c, q, sizeof(int) * n);
}
void work0() {
  static int a[(262144 + 10)];
  for (int i = 2; i <= n + 3; ++i) a[i - 2] = (998244353 - ifac[i]) % 998244353;
  getinv(a, a, n + 2);
  for (int k = 0; k <= n; ++k) g[k] = (g[k] + a[k + 1]) % 998244353;
}
void work1() {
  static int H[(262144 + 10)], P[(262144 + 10)], a[(262144 + 10)],
      b[(262144 + 10)];
  for (int i = 1; i <= n + 3; ++i)
    H[i - 1] = (-(i & 1 ? -1 : 1) * inv[i] + 998244353) % 998244353;
  getinv(H, H, n + 3);
  getpow(P, H, n + 2, n + 1);
  for (int i = 1; i <= n + 2; ++i) a[i - 1] = (998244353 - H[i]) % 998244353;
  getinv(a, a, n + 2);
  multi(b, P, a, n + 2 - 1);
  for (int k = 0; k <= n; ++k) {
    int k_ = n - k + 1;
    g[k] = ((g[k] - (long long)k_ * b[n - k_ + 2] % 998244353 * inv[n + 1]) %
                998244353 +
            998244353) %
           998244353;
  }
  multi(a, a, a, n + 2 - 1);
  for (int i = 1; i <= n + 2; ++i) b[i - 1] = (long long)H[i] * i % 998244353;
  multi(b, b, P, n + 2 - 1);
  multi(b, b, a, n + 2 - 1);
  for (int k = 0; k <= n; ++k) {
    int k_ = n - k + 1;
    g[k] = ((g[k] - (long long)b[n - k_ + 2] * inv[n + 1]) % 998244353 +
            998244353) %
           998244353;
  }
}
void work2() {
  static int a[(262144 + 10)], b[(262144 + 10)], c[(262144 + 10)];
  for (int k = 0; k <= n; ++k) a[k] = fac[k] * g[k] % 998244353;
  for (int k = 0; k <= n; ++k)
    b[n - k] = ((k & 1 ? -1 : 1) * ifac[k] + 998244353) % 998244353;
  multi(c, a, b, n);
  for (int i = 0; i < n; ++i)
    ans[i] = c[n + i] * fac[n] % 998244353 * ifac[i] % 998244353;
}
int main() {
  scanf("%d", &n);
  initC(n + 5);
  work0();
  work1();
  work2();
  ans[0] = (ans[0] - fac[n] + 998244353) % 998244353;
  for (int i = 0; i < n; ++i) printf("%d ", ans[i]);
  return 0;
}