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 = 1 << 18;
const int mod = 998244353;
inline int qp(int a, int b) {
  int res = 1;
  while (b) {
    if (b & 1) res = 1ll * res * a % mod;
    a = 1ll * a * a % mod;
    b >>= 1;
  }
  return res;
}
int fact[N + 5], ifact[N + 5], inv[N + 5];
namespace Poly {
int W[2][N + 5], rev[N + 5], stk[N + 5], last_n;
struct Init {
  inline Init() {
    inv[1] = 1;
    for (int i = 2; i <= N; i++)
      inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
    fact[0] = ifact[0] = 1;
    for (int i = 1; i <= N; i++) {
      fact[i] = 1ll * fact[i - 1] * i % mod;
      ifact[i] = 1ll * ifact[i - 1] * inv[i] % mod;
    }
    int x = qp(3, (mod - 1) / N), y = qp(x, mod - 2);
    W[0][0] = W[1][0] = 1;
    for (int i = 1; i < N; i++) {
      W[0][i] = 1ll * W[0][i - 1] * x % mod;
      W[1][i] = 1ll * W[1][i - 1] * y % mod;
    }
    last_n = -1;
    rev[0] = 0;
  }
} Init_t;
inline void pre_NTT(int n) {
  last_n = n;
  int cnt;
  for (cnt = 0; (1 << cnt) < n; cnt++)
    ;
  for (int i = 1; i < n; i++)
    rev[i] = ((rev[i >> 1] >> 1) | ((i & 1) << (cnt - 1)));
}
inline void NTT(int n, int *a, int flag) {
  if (last_n != n) pre_NTT(n);
  for (int i = 0; i < n; i++)
    if (rev[i] > i) swap(a[rev[i]], a[i]);
  for (int i = 2; i <= n; i <<= 1) {
    int i2 = i >> 1;
    for (int j = 0; j < i2; j++) stk[j] = W[flag][N / i * j];
    for (int j = 0; j < n; j += i) {
      int *p1 = a + j, *p2 = a + j + i2, *p3 = stk;
      for (int k = 0; k < i2; k++) {
        int x = *p1, y = 1ll * *p2 * *p3 % mod;
        *p1 = (x + y >= mod ? x + y - mod : x + y);
        *p2 = (x - y < 0 ? x - y + mod : x - y);
        ++p1, ++p2, ++p3;
      }
    }
  }
  if (flag) {
    for (int i = 0; i < n; i++) a[i] = 1ll * a[i] * inv[n] % mod;
  }
}
int mult_ta[N + 5], mult_tb[N + 5];
inline void poly_mult(int n, int *a, int m, int *b, int k, int *c) {
  int len;
  for (len = 1; len < n + m - 1; len <<= 1)
    ;
  for (int i = 0; i < n; i++) mult_ta[i] = a[i];
  for (int i = n; i < len; i++) mult_ta[i] = 0;
  for (int i = 0; i < m; i++) mult_tb[i] = b[i];
  for (int i = m; i < len; i++) mult_tb[i] = 0;
  NTT(len, mult_ta, 0);
  NTT(len, mult_tb, 0);
  for (int i = 0; i < len; i++)
    mult_ta[i] = 1ll * mult_ta[i] * mult_tb[i] % mod;
  NTT(len, mult_ta, 1);
  for (int i = 0; i < k; i++) c[i] = mult_ta[i];
}
int inv_ta[N + 5], inv_tb[N + 5];
inline void poly_inv(int n, int *a, int *b) {
  b[0] = qp(a[0], mod - 2);
  for (int m = 2; (m >> 1) < n; m <<= 1) {
    int mn = min(m, n);
    int len;
    for (len = 1; len < mn + m - 2; len <<= 1)
      ;
    for (int i = 0; i < mn; i++) inv_ta[i] = a[i];
    for (int i = mn; i < len; i++) inv_ta[i] = 0;
    for (int i = 0; i < (m >> 1); i++) inv_tb[i] = b[i];
    for (int i = (m >> 1); i < len; i++) inv_tb[i] = 0;
    NTT(len, inv_ta, 0);
    NTT(len, inv_tb, 0);
    for (int i = 0; i < len; i++)
      inv_ta[i] =
          (2ll - 1ll * inv_ta[i] * inv_tb[i] % mod + mod) * inv_tb[i] % mod;
    NTT(len, inv_ta, 1);
    for (int i = 0; i < m; i++) b[i] = inv_ta[i];
  }
}
inline void poly_der(int n, int *a, int *b) {
  for (int i = 0; i < n - 1; i++) b[i] = 1ll * a[i + 1] * (i + 1) % mod;
  b[n - 1] = 0;
}
inline void poly_int(int n, int *a, int *b) {
  for (int i = n; i >= 1; i--) b[i] = 1ll * a[i - 1] * inv[i] % mod;
  b[0] = 0;
}
int ln_ta[N + 5];
inline void poly_ln(int n, int *a, int *b) {
  poly_inv(n, a, b);
  poly_der(n, a, ln_ta);
  poly_mult(n, b, n - 1, ln_ta, n - 1, ln_ta);
  poly_int(n - 1, ln_ta, b);
}
int exp_ta[N + 5];
inline void poly_exp(int n, int *a, int *b) {
  b[0] = 1;
  for (int m = 2; (m >> 1) < n; m <<= 1) {
    for (int i = (m >> 1); i < m; i++) b[i] = 0;
    poly_ln(m, b, exp_ta);
    for (int i = 0; i < m; i++)
      exp_ta[i] = (mod - exp_ta[i] + (i < n ? a[i] : 0) + (i == 0)) % mod;
    poly_mult(m, b, m, exp_ta, m, b);
  }
}
int pow_ta[N + 5], pow_tb[N + 5];
inline void poly_pow(int n, int *a, int m, int *b) {
  if (!m) {
    for (int i = b[0] = 1; i < n; i++) b[i] = 0;
    return;
  }
  int p = 0;
  while (p < n && !a[p]) p++;
  if (1ll * p * m >= n) {
    for (int i = 0; i < n; i++) b[i] = 0;
    return;
  }
  int t = qp(a[p], mod - 2);
  int len = n - p * m;
  for (int i = 0; i < len; i++) pow_ta[i] = 1ll * a[i + p] * t % mod;
  poly_ln(len, pow_ta, pow_tb);
  for (int i = 0; i < len; i++) pow_tb[i] = 1ll * pow_tb[i] * m % mod;
  poly_exp(len, pow_tb, b);
  t = qp(a[p], m);
  for (int i = n - 1; i >= p * m; i--) b[i] = 1ll * b[i - p * m] * t % mod;
  for (int i = 0; i < p * m; i++) b[i] = 0;
}
}  // namespace Poly
using Poly::poly_der;
using Poly::poly_exp;
using Poly::poly_int;
using Poly::poly_inv;
using Poly::poly_ln;
using Poly::poly_mult;
using Poly::poly_pow;
int n, a[N + 5], b[N + 5], c[N + 5], d[N + 5], f[N + 5], g[N + 5], phi[N + 5],
    phi_d[N + 5], phi_pow[N + 5];
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n + 2; i++)
    a[i] = (i & 1) ? (mod - inv[i + 1]) : inv[i + 1];
  poly_inv(n + 2, a, phi);
  poly_pow(n + 2, phi, n + 1, phi_pow);
  poly_der(n + 2, phi, phi_d);
  for (int i = 0; i < n + 1; i++) b[i] = phi[i + 1] ? (mod - phi[i + 1]) : 0;
  poly_inv(n + 1, b, a);
  poly_mult(n + 1, a, n + 1, a, n + 1, b);
  poly_mult(n + 2, phi_pow, n + 1, a, n + 1, a);
  poly_mult(n + 2, phi_pow, n + 1, b, n + 1, b);
  poly_mult(n + 1, b, n + 1, phi_d, n + 1, b);
  for (int i = 0; i < n + 1; i++) c[i] = mod - ifact[i + 2];
  poly_inv(n + 1, c, d);
  for (int i = 0; i < n + 1; i++) c[i] = ifact[i + 1];
  poly_mult(n + 1, c, n + 1, d, n + 1, c);
  for (int i = 0; i < n; i++) {
    f[i] = (c[i + 1] -
            (1ll * a[i + 1] * (n - i + 1) + b[i + 1]) % mod * inv[n + 1] % mod +
            mod) %
           mod;
    f[i] = 1ll * f[i] * fact[i] % mod;
    g[n - 1 - i] = (i & 1) ? (mod - ifact[i]) : ifact[i];
  }
  poly_mult(n, f, n, g, 2 * n - 1, f);
  for (int i = 0; i < n; i++) {
    printf("%lld%c", 1ll * f[n - 1 + i] * fact[n] % mod * ifact[i] % mod,
           " \n"[i == n - 1]);
  }
  return 0;
}