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 = 4e5 + 5;
const int mod = 998244353, g = 3;
int add(int a, int b) {
  a += b;
  return a >= mod ? a - mod : a;
}
int sub(int a, int b) {
  a -= b;
  return a < 0 ? a + mod : a;
}
int mul(int a, int b) { return (long long)a * b % mod; }
int qpow(int a, int b) {
  int ret = 1;
  for (; b; b >>= 1, a = mul(a, a))
    if (b & 1) ret = mul(ret, a);
  return ret;
}
const int inv2 = qpow(2, mod - 2);
int w[N];
void init() {
  for (int step = 1; step < N; step <<= 1) {
    w[step] = qpow(g, (mod - 1) / (step << 1));
  }
}
namespace Poly_template {
int rev[N];
vector<int> Add(vector<int> a, vector<int> b) {
  a.resize(max(a.size(), b.size()));
  for (size_t i = 0; i < b.size(); i++) a[i] = add(a[i], b[i]);
  return a;
}
vector<int> Sub(vector<int> a, vector<int> b) {
  a.resize(max(a.size(), b.size()));
  for (size_t i = 0; i < b.size(); i++) a[i] = sub(a[i], b[i]);
  return a;
}
vector<int> Cross(vector<int> a, int x) {
  for (size_t i = 0; i < a.size(); i++) a[i] = mul(a[i], x);
  return a;
}
vector<int> rever(vector<int> x) {
  reverse(x.begin(), x.end());
  return x;
}
inline void DFT(int *t, int n, int tpe) {
  int l = 0;
  while (1 << l < n) ++l;
  for (int i = 1; i < n; i++)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));
  for (int i = 0; i < n; i++)
    if (rev[i] > i) swap(t[rev[i]], t[i]);
  for (int step = 1; step < n; step <<= 1) {
    int wn = w[step];
    for (int i = 0; i < n; i += step << 1) {
      int w = 1;
      for (int j = 0; j < step; j++, w = mul(w, wn)) {
        int x = t[i + j], y = mul(w, t[i + j + step]);
        t[i + j] = add(x, y);
        t[i + j + step] = sub(x, y);
      }
    }
  }
  if (tpe == 1) return;
  for (int i = 1; i < n - i; i++) swap(t[i], t[n - i]);
  int inv = qpow(n, mod - 2);
  for (int i = 0; i < n; i++) t[i] = mul(t[i], inv);
}
inline vector<int> NTT(vector<int> a, int n, vector<int> b, int m) {
  int len = n + m - 1, l = 0;
  while (1 << l < len) ++l;
  static vector<int> res;
  res.resize(1 << l);
  a.resize(1 << l), b.resize(1 << l);
  DFT(&a[0], 1 << l, 1), DFT(&b[0], 1 << l, 1);
  for (int i = 0; i < (1 << l); i++) res[i] = mul(a[i], b[i]);
  DFT(&res[0], 1 << l, -1);
  res.resize(len);
  return res;
}
vector<int> NTT(vector<int> a, vector<int> b) {
  return NTT(a, a.size(), b, b.size());
}
vector<int> Deri(vector<int> A) {
  for (size_t i = 1; i < A.size(); i++) A[i - 1] = mul(A[i], i);
  A.resize(A.size() - 1);
  return A;
}
vector<int> Inte(vector<int> A) {
  A.resize(A.size() + 1);
  for (int i = A.size() - 1; i; i--) A[i] = mul(A[i - 1], qpow(i, mod - 2));
  A[0] = 0;
  return A;
}
vector<int> Inv(vector<int> A, int n) {
  if (n == 1) return vector<int>(1, qpow(A[0], mod - 2));
  vector<int> x = Inv(A, (n + 1) >> 1);
  int len = 1 << ((int)ceil(log2(n)) + 1);
  x.resize(len), A.resize(len);
  for (int i = n; i < len; i++) A[i] = 0;
  DFT(&x[0], len, 1), DFT(&A[0], len, 1);
  for (int i = 0; i < len; i++) x[i] = mul(x[i], sub(2, mul(x[i], A[i])));
  DFT(&x[0], len, -1);
  x.resize(n);
  return x;
}
vector<int> Inv(vector<int> A) { return Inv(A, A.size()); }
vector<int> sqrt(vector<int> A, int n) {
  if (n == 1) return vector<int>(1, 1);
  vector<int> x = sqrt(A, (n + 1) >> 1);
  x.resize(n);
  A.resize(n);
  vector<int> res = Add(x, NTT(A, Inv(x)));
  res.resize(n);
  for (int i = 0; i < n; i++) res[i] = mul(res[i], inv2);
  return res;
}
vector<int> sqrt(vector<int> a) { return sqrt(a, a.size()); }
vector<int> ln(vector<int> A) {
  int len = A.size();
  A = Inte(NTT(Inv(A), Deri(A)));
  A.resize(len);
  return A;
}
vector<int> exp(vector<int> A, int n) {
  if (n == 1) return vector<int>(1, 1);
  vector<int> x = exp(A, (n + 1) >> 1), y;
  x.resize(n);
  A.resize(n);
  x = NTT(x, Add(vector<int>(1, 1), Sub(A, ln(x))));
  x.resize(n);
  return x;
}
vector<int> exp(vector<int> A) { return exp(A, A.size()); }
void Div(vector<int> A, vector<int> B, vector<int> &C, vector<int> &D) {
  int n = A.size(), m = B.size();
  vector<int> ra = rever(A), rb = rever(B);
  ra.resize(n - m + 1), rb.resize(n - m + 1);
  C = NTT(ra, Inv(rb));
  C.resize(n - m + 1);
  C = rever(C);
  D = Sub(A, NTT(C, B));
  D.resize(m);
  return;
}
}  // namespace Poly_template
using namespace Poly_template;
int n;
void output(vector<int> x) {
  for (size_t i = 0; i < x.size(); i++) {
    cerr << x[i] << " ";
  }
  puts("");
}
vector<int> phi, one_minus_phi;
inline void calcphi(int n) {
  phi.resize(n + 11);
  for (int i = 0; i <= n + 10; i++) {
    phi[i] = qpow(i, mod - 2);
    if (i % 2 == 0) phi[i] = sub(0, phi[i]);
  }
  for (int i = 0; i < n + 10; i++) phi[i] = phi[i + 1];
  phi.resize(n + 10);
  phi = Inv(phi);
}
vector<int> Pw(vector<int> a, int k, int n) {
  a.resize(n + 1);
  int h = a[0], ih = qpow(h, mod - 2);
  for (int i = 0; i <= n; i++) a[i] = mul(a[i], ih);
  a = ln(a);
  for (int i = 0; i <= n; i++) a[i] = mul(a[i], k);
  a = exp(a);
  h = qpow(h, k);
  for (int i = 0; i <= n; i++) a[i] = mul(a[i], h);
  return a;
}
vector<int> mult(vector<int> a, vector<int> b, int n) {
  vector<int> ret = NTT(a, b);
  ret.resize(n + 1);
  return ret;
}
int fac[N], ifac[N];
vector<int> G, H1, H2, F, Q, ans;
int main() {
  init();
  fac[0] = ifac[0] = 1;
  for (int i = 1; i <= 200000; i++) fac[i] = mul(fac[i - 1], i);
  ifac[200000] = qpow(fac[200000], mod - 2);
  for (int i = 199999; i; i--) ifac[i] = mul(ifac[i + 1], i + 1);
  cin >> n;
  calcphi(n);
  one_minus_phi.resize(n + 2);
  for (int i = 0; i < n + 2; i++) one_minus_phi[i] = sub(0, phi[i + 1]);
  one_minus_phi = Inv(one_minus_phi);
  G = Pw(phi, n + 1, n);
  H1 = mult(G, one_minus_phi, n);
  H2 = mult(mult(G, Deri(phi), n), mult(one_minus_phi, one_minus_phi, n), n);
  F.resize(n + 1);
  Q.resize(n + 1);
  for (int i = 0; i <= n; i++) Q[i] = sub(0, ifac[i + 2]), F[i] = ifac[i + 1];
  Q = NTT(F, Inv(Q));
  ans.resize(n);
  for (int i = 1; i <= n; i++) {
    int w =
        sub(Q[i], mul(qpow(n + 1, mod - 2), add(mul(H1[i], n + 2 - i), H2[i])));
    w = mul(w, fac[i - 1]);
    ans[i - 1] = w;
  }
  F.resize(n, 0);
  for (int i = 0; i < n; i++)
    F[i] = mul((n - 1 - i) % 2 ? mod - 1 : 1, ifac[n - 1 - i]);
  ans = NTT(ans, F);
  for (int i = 0; i < n; i++) {
    printf("%d ", mul(ans[n - 1 + i], mul(ifac[i], fac[n])));
  }
  puts("");
}