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;
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 inv_2 = qpow(2, mod - 2);
namespace polynomial {
const int Ntt_Lim = 4e5 + 5;
int inverse[N];
int rev[Ntt_Lim], _w[Ntt_Lim];
const int G_mod = 3;
vector<int> deri(vector<int> a) {
  for (int i = 0; i + 1 < (int)a.size(); i++) a[i] = mul(a[i + 1], i + 1);
  a.pop_back();
  return a;
}
vector<int> inte(vector<int> a) {
  a.push_back(0);
  for (int i = (int)a.size() - 2; ~i; i--) a[i + 1] = mul(a[i], inverse[i + 1]);
  a[0] = 0;
  return a;
}
vector<int> p_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> p_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;
}
inline void _w_init() {
  inverse[1] = 1;
  for (int i = 2; i < Ntt_Lim; i++)
    inverse[i] = mul(mod - mod / i, inverse[mod % i]);
  for (int step = 1; step * 2 <= Ntt_Lim; step <<= 1) {
    int wn = qpow(G_mod, (mod - 1) / (step << 1));
    for (int j = step, w = 1; j < step << 1; j++, w = mul(w, wn)) {
      _w[j] = w;
    }
  }
}
inline void dft(int *f, int len, int type) {
  int l = 0;
  while (1 << l < len) ++l;
  for (int i = 0; i < len; i++)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));
  for (int i = 0; i < len; i++)
    if (i < rev[i]) swap(f[i], f[rev[i]]);
  for (int step = 1; step < len; step <<= 1) {
    for (int i = 0; i < len; i += step << 1)
      for (int x, y, j = 0; j < step; j++) {
        x = f[i + j], y = mul(_w[j + step], f[i + j + step]);
        f[i + j] = add(x, y), f[i + j + step] = sub(x, y);
      }
  }
  if (type == 1) return;
  int inv = qpow(len, mod - 2);
  reverse(f + 1, f + len);
  for (int i = 0; i < len; i++) f[i] = mul(f[i], inv);
}
vector<int> ntt(vector<int> a, vector<int> b, int n, int m) {
  int l = 1;
  while (l < n + m - 1) l <<= 1;
  a.resize(l), b.resize(l);
  dft(&a[0], l, 1), dft(&b[0], l, 1);
  for (int i = 0; i < l; i++) a[i] = mul(a[i], b[i]);
  dft(&a[0], l, -1);
  a.resize(n + m - 1);
  return a;
}
vector<int> ntt(vector<int> a, vector<int> b) {
  return ntt(a, b, a.size(), b.size());
}
vector<int> inv(vector<int> &f, int n) {
  if (n == 1) return vector<int>(1, qpow(f[0], mod - 2));
  vector<int> a(&f[0], &f[n]), b = inv(f, (n + 1) / 2);
  int l = 1;
  while (l < n << 1) l <<= 1;
  a.resize(l), b.resize(l);
  dft(&a[0], l, 1), dft(&b[0], l, 1);
  for (int i = 0; i < l; i++) a[i] = mul(b[i], sub(2, mul(a[i], b[i])));
  dft(&a[0], l, -1);
  a.resize(n);
  return a;
}
vector<int> inv(vector<int> a) { return inv(a, a.size()); }
vector<int> sqrt(vector<int> &f, int n) {
  if (n == 1) return vector<int>(1, 1);
  vector<int> a(&f[0], &f[n]), b = sqrt(f, (n + 1) / 2);
  b.resize(n);
  a = ntt(a, inv(b));
  a.resize(n);
  for (int i = 0; i < n; i++) a[i] = mul(inv_2, add(a[i], b[i]));
  return a;
}
vector<int> sqrt(vector<int> a) { return sqrt(a, a.size()); }
vector<int> ln(vector<int> a) {
  int l = a.size();
  a = inte(ntt(deri(a), inv(a)));
  a.resize(l);
  return a;
}
vector<int> exp(vector<int> &f, int n) {
  if (n == 1) return vector<int>(1, 1);
  vector<int> a(n, 0), b = exp(f, (n + 1) / 2);
  b.resize(n);
  a = ln(b);
  for (int i = 0; i < n; i++) a[i] = sub(f[i], a[i]);
  a[0] = add(a[0], 1);
  a = ntt(a, b);
  a.resize(n);
  return a;
}
vector<int> exp(vector<int> a) { return exp(a, a.size()); }
pair<vector<int>, vector<int> > div(vector<int> a, vector<int> b) {
  if (a.size() < b.size()) return make_pair(vector<int>(1, 0), a);
  int n = a.size(), m = b.size();
  vector<int> ra = a, rb = b;
  reverse(ra.begin(), ra.end()), reverse(rb.begin(), rb.end());
  ra.resize(n - m + 1), rb.resize(n - m + 1);
  vector<int> c = ntt(ra, inv(rb));
  c.resize(n - m + 1);
  reverse(c.begin(), c.end());
  vector<int> d = p_sub(a, ntt(b, c));
  d.resize(m - 1);
  return make_pair(c, d);
}
}  // namespace polynomial
using namespace polynomial;
int n;
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() {
  _w_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(H1, deri(phi), n), one_minus_phi, 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 = inv(Q);
  Q = ntt(F, 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("");
}