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 double pi = acos(-1.0);
const int mod = 998244353;
void reduce(int &a) { a += a >> 31 & mod; }
int Mod(int x) { return x >= mod ? x - mod : x; }
long long read() {
  long long x = 0;
  int f = 1;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
  return x * f;
}
void print(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) print(x / 10);
  putchar(x % 10 + '0');
}
int qpow(int a, int b) {
  int ans = 1;
  for (; b; b >>= 1, a = (long long)a * a % mod)
    if (b & 1) ans = (long long)ans * a % mod;
  return ans;
}
const int N = 800010, G = 3, Gi = 332748118, inv2 = 499122177, img = 86583718;
int rev[N], ul[N], gg[20][N];
int G_init() {
  for (int i = 0; i < 20; i++) {
    int *G = gg[i];
    G[0] = 1;
    const int gi = G[1] = qpow(3, (mod - 1) / (1 << i + 1));
    for (int j = 2; j < (1 << i); j++) G[j] = (long long)G[j - 1] * gi % mod;
  }
  return 0;
}
int I = G_init();
void NTT(int *a, const int n, const int type) {
  for (int i = 0; i < n; i++)
    if (i < rev[i]) swap(a[i], a[rev[i]]);
  int lim = log(n) / log(2) + 0.5;
  for (int k = 1; k <= lim; k++) {
    const int l = 1 << k, m = l >> 1, *G = gg[k - 1];
    for (int *p = a; p != a + n; p += l)
      for (int i = 0; i < m; i++) {
        const int t = (long long)p[i + m] * G[i] % mod;
        reduce(p[i + m] = p[i] - t), reduce(p[i] += t - mod);
      }
  }
  if (~type) return;
  const int inv = qpow(n, mod - 2);
  for (int i = 0; i < n; i++) a[i] = (long long)a[i] * inv % mod;
  reverse(a + 1, a + n);
}
void calc_rev(int &n, int &lim, const int m) {
  n = 1, lim = 0;
  while (n < m) n <<= 1, lim++;
  for (int i = 1; i < n; i++)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << lim - 1);
}
void Mul(const int *a, const int *b, int *c, const int m1, const int m2) {
  static int x[N], y[N];
  int n, lim;
  calc_rev(n, lim, m1 + m2);
  for (int i = 0; i < m1; i++) x[i] = a[i];
  for (int i = m1; i < n; i++) x[i] = 0;
  for (int i = 0; i < m2; i++) y[i] = b[i];
  for (int i = m2; i < n; i++) y[i] = 0;
  NTT(x, n, 1), NTT(y, n, 1);
  for (int i = 0; i < n; i++) c[i] = (long long)x[i] * y[i] % mod;
  NTT(c, n, -1);
  for (int i = m1 + m2 - 1; i < n; i++) c[i] = 0;
}
void Inv(const int *a, int *b, const int len) {
  static int c[N];
  if (len == 1) {
    b[0] = qpow(a[0], mod - 2);
    return;
  }
  Inv(a, b, len + 1 >> 1);
  int n, lim;
  calc_rev(n, lim, len << 1);
  for (int i = 0; i < n; i++) c[i] = a[i];
  for (int i = len; i < n; i++) c[i] = 0;
  NTT(c, n, 1), NTT(b, n, 1);
  for (int i = 0; i < n; i++)
    b[i] = (2 - (long long)c[i] * b[i] % mod + mod) * b[i] % mod;
  NTT(b, n, -1);
  for (int i = len; i < n; i++) b[i] = 0;
}
void Der(const int *a, int *b, const int len) {
  for (int i = 1; i < len; i++) b[i - 1] = (long long)a[i] * i % mod;
  b[len - 1] = 0;
}
void Inte(const int *a, int *b, const int len) {
  for (int i = len - 1; i; i--)
    b[i] = (long long)a[i - 1] * qpow(i, mod - 2) % mod;
  b[0] = 0;
}
void Ln(const int *a, int *b, const int len) {
  static int c[N], inv[N];
  memset(inv, 0, len << 4);
  Der(a, c, len), Inv(a, inv, len);
  Mul(c, inv, c, len, len), Inte(c, b, len);
}
void Exp(const int *a, int *b, const int len) {
  static int c[N];
  if (len == 1) {
    b[0] = 1;
    return;
  }
  Exp(a, b, len + 1 >> 1);
  int lim, n;
  calc_rev(n, lim, len << 1);
  Ln(b, c, len);
  for (int i = 0; i < len; i++) reduce(c[i] = a[i] - c[i]);
  c[0]++;
  for (int i = len; i < n; i++) c[i] = 0;
  Mul(b, c, b, len, len);
  for (int i = len; i < n; i++) b[i] = 0;
}
void Power(const int *a, int *b, const int len, const char *k, int m = -1) {
  int m1 = 0, m2 = 0, m3 = 0;
  if (~m)
    m1 = m2 = m3 = m;
  else {
    int l = strlen(k);
    for (int i = 0; i < l; i++) {
      m1 = ((long long)m1 * 10 + (k[i] ^ 48)) % mod;
      m2 = ((long long)m2 * 10 + (k[i] ^ 48)) % (mod - 1);
    }
    for (int i = 0; i < min(6, l); i++) m3 = m3 * 10 + (k[i] ^ 48);
    if (a[0] == 0 && m3 >= len) {
      for (int i = 0; i < len; i++) b[i] = 0;
      return;
    }
  }
  static int x[N], c[N];
  long long t = 0;
  while (!a[t]) t++;
  for (int i = 0; i < len; i++) x[i] = a[i + t];
  t = t * m1;
  const int res = qpow(x[0], m2), inv = qpow(x[0], mod - 2);
  for (int i = 0; i < len; i++) x[i] = (long long)x[i] * inv % mod;
  Ln(x, b, len);
  for (int i = 0; i < len; i++) b[i] = (long long)b[i] * m1 % mod;
  Exp(b, c, len);
  for (int i = 0; i < len; i++) c[i] = (long long)c[i] * res % mod;
  for (int i = 0; i < t; i++) b[i] = 0;
  for (long long i = t; i < len; i++) b[i] = c[i - t];
}
int fac[N], ifac[N];
void init(int n) {
  fac[0] = 1;
  for (int i = 1; i <= n; i++) fac[i] = (long long)fac[i - 1] * i % mod;
  ifac[n] = qpow(fac[n], mod - 2);
  for (int i = n; i; i--) ifac[i - 1] = (long long)ifac[i] * i % mod;
}
int n, m, t1[N], t2[N], S[N];
int H[N], H1[N], H2[N], inv[N];
int ans[N];
int main() {
  n = read(), m = n + 2;
  init(n + 2);
  for (int i = 0; i < n + 1; i++) t1[i] = mod - ifac[i + 2];
  Inv(t1, S, n + 1);
  for (int i = 0; i < n; i++) S[i] = S[i + 1];
  memset(t1, 0, sizeof(t1));
  t1[0] = t1[1] = 1;
  Ln(t1, t2, m + 2);
  for (int i = 0; i < m + 1; i++) t1[i] = t2[i + 1];
  Inv(t1, H, m + 1);
  Power(H, H1, m + 1, "", n + 1);
  Der(H, t1, m + 1);
  Mul(t1, H1, H2, m + 1, m + 1);
  for (int i = 0; i < m; i++) t1[i] = mod - H[i + 1];
  Inv(t1, inv, m);
  Mul(H1, inv, H1, m, m), Mul(H2, inv, H2, m, m), Mul(H2, inv, H2, m + 1, m);
  int invn = qpow(n + 1, mod - 2);
  for (int k = 0; k < n; k++) {
    int m = n - k + 1;
    reduce(S[k] -=
           ((long long)H1[n - m + 2] * m + H2[n - m + 2]) % mod * invn % mod);
  }
  S[0]--;
  memset(t1, 0, sizeof(t1)), memset(t2, 0, sizeof(t2));
  for (int i = 0; i < n; i++)
    if (i & 1)
      t1[n - i - 1] = mod - ifac[i];
    else
      t1[n - i - 1] = ifac[i];
  for (int i = 0; i < n; i++) t2[i] = (long long)S[i] * fac[i] % mod;
  Mul(t1, t2, ans, n, n);
  for (int i = 0; i < n; i++)
    print((long long)ans[i + n - 1] * ifac[i] % mod * fac[n] % mod),
        putchar(' ');
  return 0;
}