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 N = 1e6 + 7, p = 998244353;
long long wn[N << 2], iwn[N << 2];
int n, k, lim, w[N], f[N], g[N], a[N], b[N], h[N], t[N], v[N], f1[N], f2[N],
    f3[N], rev[N], ans[N], fac[N], ifac[N];
inline int read() {
  int num = 0;
  char g = getchar();
  while (g < 48 || 57 < g) g = getchar();
  while (47 < g && g < 58)
    num = (num << 1) + (num << 3) + g - 48, g = getchar();
  return num;
}
inline long long pows(long long u, int v) {
  long long ans = 1;
  while (v > 0) {
    if (v & 1) ans = ans * u % p;
    u = u * u % p, v = v >> 1;
  }
  return ans;
}
inline int inc(int a, int b) {
  if (a + b >= p) return a + b - p;
  return a + b;
}
inline int sub(int a, int b) {
  if (a - b < 0) return a - b + p;
  return a - b;
}
inline void ntt(int *s) {
  for (int i = 0; i < lim; i++)
    if (i < rev[i]) swap(s[i], s[rev[i]]);
  for (int d = 1; d < lim; d = d << 1) {
    for (int i = 0, r = d << 1; i < lim; i += r) {
      for (int j = 0; j < d; j++) {
        int a = s[i + j], b = s[i + j + d] * wn[d + j] % p;
        s[i + j] = inc(a, b), s[i + j + d] = sub(a, b);
      }
    }
  }
}
inline void intt(int *s) {
  for (int i = 0; i < lim; i++)
    if (i < rev[i]) swap(s[i], s[rev[i]]);
  for (int d = 1; d < lim; d = d << 1) {
    for (int i = 0, r = d << 1; i < lim; i += r) {
      for (int j = 0; j < d; j++) {
        int a = s[i + j], b = s[i + j + d] * iwn[d + j] % p;
        s[i + j] = inc(a, b), s[i + j + d] = sub(a, b);
      }
    }
  }
  long long inv = pows(lim, p - 2);
  for (int i = 0; i < lim; i++) s[i] = s[i] * inv % p;
}
inline void getinv(int len) {
  if (len == 1) {
    f[0] = pows(h[0], p - 2);
    return;
  }
  int d = (len + 1) / 2;
  getinv(d);
  lim = 1, k = 0;
  while (lim <= len * 2 + 1) lim = lim << 1, k++;
  for (int i = 0; i < lim; i++)
    rev[i] = (rev[i >> 1] >> 1) | (i & 1) << (k - 1), a[i] = 0, b[i] = 0;
  for (int i = 0; i < d; i++) a[i] = f[i];
  for (int i = 0; i < len; i++) b[i] = h[i];
  ntt(a), ntt(b);
  for (int i = 0; i < lim; i++) a[i] = 1ll * a[i] * a[i] % p * b[i] % p;
  intt(a);
  for (int i = 0; i < d; i++) f[i] = sub(inc(f[i], f[i]), a[i]);
  for (int i = d; i < len; i++) f[i] = p - a[i];
}
inline void getln(int len) {
  for (int i = 0; i < len; i++) h[i] = g[i];
  getinv(len);
  lim = 1, k = 0;
  while (lim <= len * 2 + 1) lim = lim << 1, k++;
  for (int i = 0; i < lim; i++)
    rev[i] = (rev[i >> 1] >> 1) | (i & 1) << (k - 1), a[i] = 0, b[i] = 0;
  for (int i = len - 1; i >= 1; i--) a[i - 1] = 1ll * g[i] * i % p;
  for (int i = 0; i < len; i++) b[i] = f[i];
  ntt(a), ntt(b);
  for (int i = 0; i < lim; i++) a[i] = 1ll * a[i] * b[i] % p;
  intt(a);
  for (int i = 1; i < len; i++) g[i] = a[i - 1] * pows(i, p - 2) % p;
  g[0] = 0;
}
inline void init() {
  for (int i = 1; i < 1e6; i = i << 1) {
    long long a = pows(3, (p - 1) / (i << 1)),
              b = pows((p + 1) / 3, (p - 1) / (i << 1)), wa = 1, wb = 1;
    for (int j = 0; j < i; j++, wa = wa * a % p, wb = wb * b % p)
      wn[i + j] = wa, iwn[i + j] = wb;
  }
}
int main() {
  init();
  cin >> n;
  g[0] = g[1] = 1;
  getln(n + 6);
  fac[0] = fac[1] = ifac[0] = ifac[1] = 1;
  for (int i = 2; i <= n + 4; i++)
    fac[i] = 1ll * fac[i - 1] * i % p, ifac[i] = pows(fac[i], p - 2);
  for (int i = 0; i <= n + 4; i++) h[i] = g[i + 1];
  getinv(n + 5);
  for (int i = 0; i <= n + 4; i++) t[i] = f[i];
  for (int i = 1; i <= n + 4; i++) h[i - 1] = (p - f[i]) % p;
  getinv(n + 4);
  for (int i = 0; i <= n + 4; i++) v[i] = f[i];
  for (int i = 0; i <= n + 4; i++) f1[i] = t[i];
  int g = n + 1;
  bool fl = 0;
  lim = 1, k = 0;
  while (lim <= n * 2 + 10) lim = lim << 1, k++;
  for (int i = 0; i < lim; i++)
    rev[i] = (rev[i >> 1] >> 1) | (i & 1) << (k - 1);
  while (g > 0) {
    if (g & 1) {
      if (!fl) {
        for (int i = 0; i <= n + 4; i++) f2[i] = f1[i];
        fl = 1;
      } else {
        for (int i = n + 5; i < lim; i++) f1[i] = 0, f2[i] = 0;
        for (int i = 0; i <= n + 4; i++) f3[i] = f1[i];
        ntt(f1), ntt(f2);
        for (int i = 0; i < lim; i++) f2[i] = 1ll * f1[i] * f2[i] % p;
        intt(f2);
        for (int i = 0; i <= n + 4; i++) f1[i] = f3[i];
        for (int i = n + 5; i < lim; i++) f1[i] = f2[i] = 0;
      }
    }
    g = g >> 1;
    if (g == 0) break;
    for (int i = n + 5; i < lim; i++) f1[i] = 0;
    ntt(f1);
    for (int i = 0; i < lim; i++) f1[i] = 1ll * f1[i] * f1[i] % p;
    intt(f1);
    for (int i = n + 5; i < lim; i++) f1[i] = 0;
  }
  for (int i = 0; i < lim; i++) a[i] = b[i] = 0;
  for (int i = 0; i <= n + 4; i++) a[i] = v[i], b[i] = f2[i];
  ntt(a), ntt(b);
  for (int i = 0; i < lim; i++) a[i] = 1ll * a[i] * b[i] % p;
  intt(a);
  for (int i = 0; i <= n; i++)
    ans[i] = (ans[i] + 1ll * a[i + 1] * (n - i + 1)) % p;
  for (int i = n + 5; i < lim; i++) a[i] = 0, b[i] = 0;
  for (int i = 0; i <= n + 4; i++) b[i] = v[i];
  ntt(a), ntt(b);
  for (int i = 0; i < lim; i++) a[i] = 1ll * a[i] * b[i] % p;
  intt(a);
  for (int i = n + 5; i < lim; i++) a[i] = 0, b[i] = 0;
  for (int i = 0; i <= n + 4; i++) b[i] = 1ll * t[i + 1] * (i + 1) % p;
  ntt(a), ntt(b);
  for (int i = 0; i < lim; i++) a[i] = 1ll * a[i] * b[i] % p;
  intt(a);
  for (int i = 0; i <= n; i++)
    ans[i] = 1ll * (ans[i] + a[i + 1]) % p * pows(n + 1, p - 2) % p;
  for (int i = 0; i < lim; i++) a[i] = 0;
  a[0] = 1;
  for (int i = 1; i <= n + 5; i++) a[i] = a[i - 1] * pows(i + 1, p - 2) % p;
  for (int i = 0; i <= n + 5; i++) h[i] = (p - a[i + 1]) % p;
  getinv(n + 5);
  for (int i = 0; i <= n + 4; i++) b[i] = f[i];
  for (int i = 0; i <= n; i++) ans[i] = (b[i + 1] - ans[i] + p) % p;
  ans[0]--;
  lim = 1, k = 0;
  while (lim <= n * 2 + 10) lim = lim << 1, k++;
  for (int i = 0; i < lim; i++) a[i] = b[i] = 0;
  for (int i = 0; i < n; i++) a[i] = 1ll * ans[i] * fac[i] % p;
  for (int i = 0; i <= n; i++) b[n - i] = (i & 1) ? (p - ifac[i]) % p : ifac[i];
  ntt(a), ntt(b);
  for (int i = 0; i < lim; i++) a[i] = 1ll * a[i] * b[i] % p;
  intt(a);
  for (int i = 1; i <= n; i++)
    printf("%d ", 1ll * fac[n] * ifac[i - 1] % p * a[n + i - 1] % p);
}