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 _G = 3, mod = 998244353, Maxn = 135000;
long long powM(long long a, long long t = mod - 2) {
  long long ans = 1;
  while (t) {
    if (t & 1) ans = ans * a % mod;
    a = a * a % mod;
    t >>= 1;
  }
  return ans;
}
const int invG = powM(_G);
int tr[Maxn << 1], tf;
void tpre(int n) {
  if (tf == n) return;
  tf = n;
  for (int i = 0; i < n; i++)
    tr[i] = (tr[i >> 1] >> 1) | ((i & 1) ? n >> 1 : 0);
}
void NTT(long long *g, bool op, int n) {
  tpre(n);
  static unsigned long long f[Maxn << 1], w[Maxn] = {1};
  for (int i = 0; i < n; i++) f[i] = (((long long)mod << 5) + g[tr[i]]) % mod;
  for (int l = 1; l < n; l <<= 1) {
    unsigned long long tG = powM(op ? _G : invG, (mod - 1) / (l + l));
    for (int i = 1; i < l; i++) w[i] = w[i - 1] * tG % mod;
    for (int k = 0; k < n; k += l + l)
      for (int p = 0; p < l; p++) {
        int tt = w[p] * f[k | l | p] % mod;
        f[k | l | p] = f[k | p] + mod - tt;
        f[k | p] += tt;
      }
    if (l == (1 << 10))
      for (int i = 0; i < n; i++) f[i] %= mod;
  }
  if (!op) {
    unsigned long long invn = powM(n);
    for (int i = 0; i < n; ++i) g[i] = f[i] % mod * invn % mod;
  } else
    for (int i = 0; i < n; ++i) g[i] = f[i] % mod;
}
void px(long long *f, long long *g, int n) {
  for (int i = 0; i < n; ++i) f[i] = f[i] * g[i] % mod;
}
void times(long long *f, long long *g, int m) {
  int n = 1;
  while (n < m + m) n <<= 1;
  NTT(f, 1, n);
  NTT(g, 1, n);
  px(f, g, n);
  NTT(f, 0, n);
  memset(f + m, 0, sizeof(long long) * (n - m));
}
void invp(long long *f, int m) {
  static long long sav[Maxn << 1], w[Maxn << 1], r[Maxn << 1];
  int n;
  for (n = 1; n < m; n <<= 1)
    ;
  w[0] = powM(f[0]);
  for (int len = 2; len <= n; len <<= 1) {
    for (int i = 0; i < (len >> 1); i++) r[i] = (w[i] << 1) % mod;
    memcpy(sav, f, sizeof(long long) * (len));
    NTT(w, 1, len << 1);
    px(w, w, len << 1);
    NTT(sav, 1, len << 1);
    px(w, sav, len << 1);
    NTT(w, 0, len << 1);
    memset(w + len, 0, sizeof(long long) * (len));
    for (int i = 0; i < len; i++) w[i] = (r[i] - w[i] + mod) % mod;
  }
  memcpy(f, w, sizeof(long long) * (m));
  memset(sav, 0, sizeof(long long) * (n + n));
  memset(w, 0, sizeof(long long) * (n + n));
  memset(r, 0, sizeof(long long) * (n + n));
}
void dao(long long *f, int m) {
  for (int i = 1; i < m; i++) f[i - 1] = f[i] * i % mod;
  f[m - 1] = 0;
}
void powp(long long *f, int m, int t) {
  static long long g[Maxn << 1];
  int n = 1;
  while (n < m + m) n <<= 1;
  g[0] = 1;
  while (t) {
    NTT(f, 1, n);
    if (t & 1) {
      NTT(g, 1, n);
      px(g, f, n);
      NTT(g, 0, n);
      memset(g + m, 0, sizeof(long long) * (n - m));
    }
    px(f, f, n);
    NTT(f, 0, n);
    memset(f + m, 0, sizeof(long long) * (n - m));
    t >>= 1;
  }
  memcpy(f, g, sizeof(long long) * (m));
  memset(f + m, 0, sizeof(long long) * (n - m));
  memset(g, 0, sizeof(long long) * (n));
}
long long fac[Maxn], ifac[Maxn];
void Init(int m) {
  fac[0] = 1;
  for (int i = 1; i <= m; i++) fac[i] = fac[i - 1] * i % mod;
  ifac[m] = powM(fac[m]);
  for (int i = m; i; i--) ifac[i - 1] = ifac[i] * i % mod;
}
int n, m;
long long F[Maxn << 1], G[Maxn << 1], S[Maxn << 1], H[Maxn << 1], H1[Maxn << 1],
    H2[Maxn << 1];
int main() {
  scanf("%d", &n);
  Init(n + 6);
  int len = 1;
  while (len < n + n + 4) len <<= 1;
  m = n + 2;
  for (int i = 0; i < m + 1; i++) G[i] = mod - ifac[i + 2];
  invp(G, m + 1);
  memcpy(S, G + 1, sizeof(long long) * (m + 1));
  for (int i = 0; i < m + 1; i++) {
    H[i] = fac[i] * ifac[i + 1] % mod;
    if (i & 1) H[i] = mod - H[i];
  }
  invp(H, m + 1);
  memcpy(H1, H, sizeof(long long) * (m));
  powp(H1, m, n + 1);
  memcpy(G, H, sizeof(long long) * (m + 1));
  dao(G, m + 1);
  memcpy(H2, H1, sizeof(long long) * (m));
  times(H2, G, m);
  memset(G, 0, sizeof(long long) * (len));
  for (int i = 0; i < m; i++) G[i] = mod - H[i + 1];
  invp(G, m);
  NTT(G, 1, len);
  NTT(H1, 1, len);
  NTT(H2, 1, len);
  px(H1, G, len);
  NTT(H1, 0, len);
  memset(H1 + m, 0, sizeof(long long) * (len - m));
  px(H2, G, len);
  NTT(H2, 0, len);
  memset(H2 + m, 0, sizeof(long long) * (len - m));
  NTT(H2, 1, len);
  px(H2, G, len);
  NTT(H2, 0, len);
  memset(H2 + m, 0, sizeof(long long) * (len - m));
  for (int i = 1, sav = powM(n + 1); i < n + 2; i++) {
    int m = n - i + 1;
    S[i] = (S[i] - (H1[n - m + 2] * m + H2[n - m + 2]) % mod * sav) % mod;
  }
  S[0] = n;
  for (int i = 0; i < n; i++) S[i] = (S[i] + mod) % mod * fac[i] % mod;
  for (int i = 0; i < n; i++) F[i] = (i & 1) ? mod - ifac[i] : ifac[i];
  memset(F + n, 0, sizeof(long long) * (len - n));
  memset(S + n, 0, sizeof(long long) * (len - n));
  reverse(S, S + n);
  NTT(F, 1, len);
  NTT(S, 1, len);
  px(S, F, len);
  NTT(S, 0, len);
  memset(S + n, 0, sizeof(long long) * (len - n));
  reverse(S, S + n);
  for (int i = 0; i < n; i++)
    printf("%lld ", S[i] * fac[n] % mod * ifac[i] % mod);
  return 0;
}