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;
template <typename T>
bool chkmax(T& x, T y) {
  return x < y ? x = y, true : false;
}
template <typename T>
bool chkmin(T& x, T y) {
  return x > y ? x = y, true : false;
}
long long rd() {
  long long k = 0, f = 1;
  char c = getchar();
  while (!isdigit(c)) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (isdigit(c)) {
    k = (k << 1) + (k << 3) + c - 48;
    c = getchar();
  }
  return k * f;
}
void wr(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) wr(x / 10);
  putchar(x % 10 + '0');
}
const int cys = 998244353, g = 3, invg = (cys + 1) / 3;
int n;
long long ni[200015], fac[200015], inv[200015], tw[200005];
int mod(int x) { return x >= cys ? x - cys : x; }
long long qpow(long long x, long long p) {
  long long ret = 1;
  for (; p; p >>= 1, x = x * x % cys)
    if (p & 1) ret = ret * x % cys;
  return ret;
}
vector<long long> operator+(vector<long long> a, vector<long long> b) {
  vector<long long> ret(max(a.size(), b.size()));
  for (int i = 0; i < ret.size(); i++)
    ret[i] = mod((i < a.size() ? a[i] : 0) + (i < b.size() ? b[i] : 0));
  return ret;
}
vector<long long> operator-(vector<long long> a, vector<long long> b) {
  vector<long long> ret(max(a.size(), b.size()));
  for (int i = 0; i < ret.size(); i++)
    ret[i] = mod((i < a.size() ? a[i] : 0) + cys - (i < b.size() ? b[i] : 0));
  return ret;
}
vector<long long> operator*(vector<long long> a, long long b) {
  for (int i = 0; i < a.size(); i++) a[i] = 1ll * a[i] * b % cys;
  return a;
}
vector<long long> operator>>(vector<long long> a, int b) {
  for (int i = 0; i < a.size() - b; i++) a[i] = a[i + b];
  a.resize(a.size() - b);
  return a;
}
namespace poly {
int N, l;
int A[1100000], B[1100000], r[1100000], pre1[20][600000], pre2[20][600000];
void pre() {
  for (int i = 1, r = 0; i < (1 << 19); i <<= 1, r++) {
    int w = 1, wn = qpow(g, (cys - 1) / (i << 1));
    for (int j = 0; j < i; j++, w = 1ll * w * wn % cys) pre1[r][j] = w;
  }
  for (int i = 1, r = 0; i < (1 << 19); i <<= 1, r++) {
    int w = 1, wn = qpow(invg, (cys - 1) / (i << 1));
    for (int j = 0; j < i; j++, w = 1ll * w * wn % cys) pre2[r][j] = w;
  }
}
void ntt(int* A, int N, int f) {
  for (int i = 0; i < N; i++)
    if (i < r[i]) swap(A[i], A[r[i]]);
  for (int i = 1, r = 0; i < N; i <<= 1, r++) {
    for (int j = 0; j < N; j += (i << 1)) {
      for (int k = j; k < j + i; k++) {
        int x = A[k], y = 1ll * A[k + i] *
                          (f > 0 ? pre1[r][k - j] : pre2[r][k - j]) % cys;
        A[k] = mod(x + y);
        A[k + i] = mod(x + cys - y);
      }
    }
  }
  if (f < 0) {
    int invn = qpow(N, cys - 2);
    for (int i = 0; i < N; i++) A[i] = 1ll * A[i] * invn % cys;
  }
}
void init(int t) {
  N = 1, l = 0;
  for (; N < t; N <<= 1) l++;
  for (int i = 0; i < N; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
}
void getmul() {
  ntt(A, N, 1);
  ntt(B, N, 1);
  for (int i = 0; i < N; i++) A[i] = 1ll * A[i] * B[i] % cys;
  ntt(A, N, -1);
}
vector<long long> mul(vector<long long> a, vector<long long> b) {
  init(a.size() + b.size());
  for (int i = 0; i < N; i++) A[i] = i < a.size() ? a[i] : 0;
  for (int i = 0; i < N; i++) B[i] = i < b.size() ? b[i] : 0;
  getmul();
  vector<long long> ret(a.size() + b.size() - 1);
  for (int i = 0; i < ret.size(); i++) ret[i] = A[i];
  return ret;
}
vector<long long> polyinv(vector<long long> a, int l) {
  if (l == 1) return vector<long long>(1, qpow(a[0], cys - 2));
  a.resize(l);
  vector<long long> b = polyinv(a, (l + 1) / 2);
  init(l << 1);
  for (int i = 0; i < N; i++) A[i] = i < l ? a[i] : 0;
  for (int i = 0; i < N; i++) B[i] = i < (l + 1) / 2 ? b[i] : 0;
  ntt(A, N, 1);
  ntt(B, N, 1);
  for (int i = 0; i < N; i++) A[i] = 1ll * A[i] * B[i] % cys * B[i] % cys;
  ntt(A, N, -1);
  vector<long long> t = b * 2;
  t.resize(l);
  for (int i = 0; i < l; i++) t[i] = mod(t[i] + cys - A[i]);
  return t;
}
vector<long long> polydiff(vector<long long> a) {
  for (int i = 0; i < a.size() - 1; i++) a[i] = 1ll * (i + 1) * a[i + 1] % cys;
  a.resize(a.size() - 1);
  return a;
}
vector<long long> polyint(vector<long long> a) {
  a.resize(a.size() + 1);
  for (int i = a.size() - 1; i >= 1; i--) a[i] = 1ll * a[i - 1] * ni[i] % cys;
  a[0] = 0;
  return a;
}
vector<long long> polyln(vector<long long> a, int l) {
  return polyint(mul(polydiff(a), polyinv(a, l)));
}
vector<long long> polyexp(vector<long long> a, int l) {
  if (l == 1) return vector<long long>(1, 1);
  a.resize(l);
  vector<long long> b = polyexp(a, (l + 1) / 2);
  init(l << 1);
  vector<long long> t = mul(b, vector<long long>(1, 1) - polyln(b, l) + a);
  t.resize(l);
  return t;
}
vector<long long> polypow(vector<long long> a, int l, int k) {
  return polyexp(polyln(a, l) * k, l);
}
}  // namespace poly
vector<long long> getans() {
  vector<long long> f(0);
  for (int i = 0; i <= n + 1; i++) f.push_back(inv[i + 1]);
  vector<long long> tmp =
      poly::mul(f, poly::polyinv((vector<long long>(1, 1) - f) >> 1, n + 1));
  vector<long long> tw(0);
  tw.resize(n);
  for (int i = 0; i < n; i++) tw[i] = tmp[i + 1];
  vector<long long> h(0);
  h.push_back(1), h.push_back(1);
  h = poly::polyinv(poly::polyln(h, n + 3) >> 1, n + 2);
  vector<long long> g =
      poly::polyinv((vector<long long>(1, 1) - h) >> 1, n + 1);
  vector<long long> ph = poly::polypow(h, n + 1, n + 1);
  vector<long long> t1 = poly::mul(g, ph);
  vector<long long> tmp1 = poly::mul(poly::polydiff(h), ph);
  tmp1.resize(n + 1);
  vector<long long> tmp2 = poly::mul(g, g);
  tmp2.resize(n + 1);
  vector<long long> t2 = poly::mul(tmp1, tmp2);
  for (int i = 0; i < n; i++)
    tw[i] =
        mod(tw[i] + cys -
            ni[n + 1] * mod(t1[i + 1] * (n - i + 1) % cys + t2[i + 1]) % cys);
  for (int i = 0; i < n; i++) tw[i] = tw[i] * fac[i] % cys;
  reverse(tw.begin(), tw.end());
  tmp.clear();
  for (int i = 0; i < n; i++) tmp.push_back(i & 1 ? cys - inv[i] : inv[i]);
  tw = poly::mul(tw, tmp);
  tw.resize(n);
  reverse(tw.begin(), tw.end());
  return tw;
}
int main() {
  poly::pre();
  n = rd();
  fac[0] = inv[0] = 1;
  for (int i = 1; i <= n + 5; i++) fac[i] = fac[i - 1] * i % cys;
  inv[n + 5] = qpow(fac[n + 5], cys - 2);
  for (int i = n + 4; i >= 1; i--) inv[i] = inv[i + 1] * (i + 1) % cys;
  for (int i = 1; i <= n + 5; i++) ni[i] = inv[i] * fac[i - 1] % cys;
  vector<long long> res = getans();
  for (int i = 0; i < n; i++)
    wr(res[i] * fac[n] % cys * inv[i] % cys), putchar(' ');
  printf("\n");
  return 0;
}