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;
inline long long rd() {
  long long x = 0, w = 1;
  char c = getchar();
  while (!isdigit(c) && c != '-') c = getchar();
  if (c == '-') c = getchar(), w = -1;
  while (isdigit(c)) x = x * 10 + c - 48, c = getchar();
  return x * w;
}
const int N = 300000, P = 998244353, iv2 = (P + 1) / 2;
int fac[N], ifac[N], iv[N];
inline int pls(int a, int b) {
  a += b;
  return a >= P ? a - P : a;
}
inline int pw(int a, int b) {
  int r = 1;
  for (; b; b >>= 1, a = 1ll * a * a % P)
    if (b & 1) r = 1ll * r * a % P;
  return r;
}
namespace poly {
int r[N];
int *w[18];
void init() {
  for (int i = 2, t = 0; i < N; i <<= 1, t++) {
    w[t] = new int[i >> 1];
    int wn = pw(3, (P - 1) / i);
    w[t][0] = 1;
    for (int j = (1); j < ((i >> 1)); ++j) w[t][j] = 1ll * w[t][j - 1] * wn % P;
  }
}
inline void ntt(int n, int *a, int f) {
  int l = 1;
  while ((1 << l) < n) l++;
  for (int i = (1); i < (n); ++i) r[i] = r[i >> 1] >> 1 | (i & 1) << (l - 1);
  for (int i = (0); i < (n); ++i)
    if (i < r[i]) swap(a[i], a[r[i]]);
  for (int i = 2, t = 0; i <= n; i <<= 1, t++) {
    for (int j = 0; j < n; j += i) {
      int *x = a + j, *y = a + j + (i >> 1);
      for (int k = (0); k < ((i >> 1)); ++k) {
        int v = 1ll * y[k] * w[t][k] % P;
        y[k] = pls(x[k], P - v);
        x[k] = pls(x[k], v);
      }
    }
  }
  if (f == -1) {
    reverse(a + 1, a + n);
    int ivn = iv[n];
    for (int i = (0); i < (n); ++i) a[i] = 1ll * a[i] * ivn % P;
  }
}
inline void mul(int n, int *a, int *b) {
  if (n <= 64) {
    static unsigned long long tmp[130];
    int m = n >> 1;
    for (int i = (0); i < (m); ++i)
      for (int j = (0); j < (m); ++j) tmp[i + j] += 1ll * a[i] * b[j];
    for (int i = (0); i < (n); ++i) a[i] = tmp[i] % P, tmp[i] = 0;
    return;
  }
  ntt(n, a, 1);
  ntt(n, b, 1);
  for (int i = (0); i < (n); ++i) a[i] = 1ll * a[i] * b[i] % P;
  ntt(n, a, -1);
}
int t1[N];
void inv(int n, int *a, int *b) {
  if (n == 1) {
    b[0] = pw(a[0], P - 2);
    b[1] = 0;
    return;
  }
  inv(n >> 1, a, b);
  int m = n << 1;
  memset(b + n, 0, n * 4);
  memset(t1 + n, 0, n * 4);
  for (int i = (0); i < (n); ++i) t1[i] = a[i];
  ntt(m, b, 1);
  ntt(m, t1, 1);
  for (int i = (0); i < (m); ++i)
    b[i] = 1ll * (2ll + P - 1ll * t1[i] * b[i] % P) * b[i] % P;
  ntt(m, b, -1);
  memset(b + n, 0, n * 4);
}
inline void deri(int n, int *a) {
  for (int i = (1); i < (n); ++i) a[i - 1] = 1ll * i * a[i] % P;
  a[n - 1] = 0;
}
inline void inte(int n, int *a) {
  for (int i = (n - 1); i >= (1); --i) a[i] = 1ll * a[i - 1] * iv[i] % P;
  a[0] = 0;
}
int t2[N];
void ln(int n, int *a, int *b) {
  int m = n << 1;
  memset(b, 0, m * 4);
  memset(t2, 0, m * 4);
  inv(n, a, b);
  for (int i = (0); i < (n); ++i) t2[i] = a[i];
  deri(n, t2);
  mul(m, b, t2);
  memset(b + n, 0, n * 4);
  inte(n, b);
}
int t3[N];
void exp(int n, int *a, int *b) {
  if (n == 1) {
    b[0] = 1;
    b[1] = 0;
    return;
  }
  exp(n >> 1, a, b);
  int m = n << 1;
  memset(b + n, 0, n * 4);
  memset(t3, 0, m * 4);
  ln(n, b, t3);
  for (int i = (0); i < (n); ++i) swap(b[i], t3[i]);
  for (int i = (0); i < (n); ++i) b[i] = (a[i] + P - b[i]) % P;
  b[0]++;
  mul(m, b, t3);
  memset(b + n, 0, n * 4);
}
int t4[N];
void pwk(int n, int k, int *a, int *b) {
  ln(n, a, t4);
  for (int i = (0); i < (n); ++i) t4[i] = 1ll * t4[i] * k % P;
  exp(n, t4, b);
}
}  // namespace poly
using namespace poly;
int tA[N], tB[N];
inline void mul(int nn, int mm, int *A, int *B, int *C, int o = 0) {
  for (int i = (0); i < (nn); ++i) tA[i] = A[i], tB[i] = B[i];
  memset(tA + nn, 0, nn * 4);
  memset(tB + nn, 0, nn * 4);
  ntt(mm, tA, 1);
  ntt(mm, tB, 1);
  for (int i = (0); i < (mm); ++i) C[i] = 1ll * tA[i] * tB[i] % P;
  ntt(mm, C, -1);
  if (!o) memset(C + nn, 0, nn * 4);
}
int n, nn, mm, A[N], B[N], C[N], D[N], H[N], H1[N], H2[N], iH[N], E[N], F[N],
    G[N], Lx[N], Rx[N], S[N], ans[N];
int main() {
  n = rd();
  nn = 1;
  while (nn <= n + 10) nn <<= 1;
  mm = nn << 1;
  init();
  fac[0] = 1;
  for (int i = (1); i < (N); ++i) fac[i] = 1ll * fac[i - 1] * i % P;
  ifac[0] = 1;
  for (int i = (1); i < (N); ++i) ifac[i] = pw(fac[i], P - 2);
  iv[1] = 1;
  for (int i = (2); i < (N); ++i) iv[i] = 1ll * (P - P / i) * iv[P % i] % P;
  A[0] = 1;
  A[1] = 1;
  ln(nn, A, B);
  for (int i = (0); i < (nn); ++i) B[i] = B[i + 1];
  inv(nn, B, H);
  for (int i = (0); i < (nn); ++i) H1[i] = 1ll * H[i + 1] * (i + 1) % P;
  pwk(nn, n + 1, H, H2);
  for (int i = (0); i < (nn); ++i) D[i] = P - H[i + 1];
  inv(nn, D, iH);
  mul(nn, mm, H2, iH, Rx);
  mul(nn, mm, iH, iH, iH);
  mul(nn, mm, iH, H1, Lx);
  mul(nn, mm, Lx, H2, Lx);
  for (int i = (0); i <= (n + 1); ++i)
    S[i] = (Lx[n - i + 2] + 1ll * i * Rx[n - i + 2]) % P * iv[n + 1] % P;
  reverse(S, S + n + 2);
  for (int i = (0); i < (nn); ++i) G[i] = P - ifac[i + 2];
  inv(nn, G, E);
  for (int i = (0); i < (nn); ++i) E[i] = E[i + 1];
  for (int i = (0); i <= (n + 1); ++i) S[i] = (E[i] + P - S[i]) % P;
  S[0] = n;
  for (int i = (0); i <= (n + 1); ++i) S[i] = 1ll * S[i] * fac[i] % P;
  for (int i = (0); i <= (n); ++i)
    F[i] = 1ll * ((n - i) & 1 ? P - 1 : 1) * ifac[n - i] % P;
  mul(nn, mm, S, F, C, 1);
  for (int i = (0); i <= (n); ++i)
    ans[i] = 1ll * C[n + i] * fac[n] % P * ifac[i] % P;
  for (int i = (0); i < (n); ++i) printf("%d ", ans[i]);
  return 0;
}