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;
namespace poly {
const int LM = (1 << 22), mod = 998244353;
int lm, lg[LM + 10], rev[LM + 10], rt[LM + 10][2], iv[LM + 10], *p, *q;
int POW(int x, int y) {
  int ret = 1;
  while (y)
    y& 1 ? ret = 1ll * ret * x % mod : 0, x = 1ll * x * x % mod, y >>= 1;
  return ret;
}
void NTT(vector<int>& f, const int& op) {
  int tn = f.size(), l = lg[tn], r, t1, t2;
  long long nr;
  for (int i = 0; i < tn; ++i)
    rev[i] = (rev[i >> 1] >> 1) + (i & 1) * (1 << l - 1),
    rev[i] < i ? swap(f[rev[i]], f[i]), 0 : 0;
  for (int i = 2; i <= tn; i <<= 1) {
    r = rt[i][op];
    for (int j = 0; j < tn; j += i) {
      nr = 1, p = &f[j], q = &f[j + (i >> 1)];
      for (int k = j; k < j + (i >> 1); ++k, nr = nr * r % mod, ++p, ++q)
        t1 = *p, t2 = nr * (*q) % mod,
        (*p) -= (((*p) = t1 + t2) >= mod ? mod : 0), (*q) = t1 - t2,
        ((*q) += ((*q) >> 31) & mod);
    }
  }
  if (op)
    for (int i = 0; i < tn; ++i) f[i] = 1ll * f[i] * iv[tn] % mod;
}
vector<int> Poly(const int& x) {
  vector<int> ret;
  return ret.push_back(x), ret;
}
vector<int> Plus(vector<int> x, vector<int> y) {
  int sz = max(x.size(), y.size());
  x.resize(sz), y.resize(sz);
  for (int i = 0; i < sz; ++i) (x[i] += y[i]) >= mod ? x[i] -= mod : 0;
  return x;
}
vector<int> Minus(vector<int> x, vector<int> y) {
  int sz = max(x.size(), y.size());
  x.resize(sz), y.resize(sz);
  for (int i = 0; i < sz; ++i) x[i] -= y[i], (x[i] += (x[i] >> 31) & mod);
  return x;
}
vector<int> Mul(vector<int> x, const int& y) {
  for (int i = 0; i < x.size(); ++i) x[i] = 1ll * x[i] * y % mod;
  return x;
}
vector<int> Mul(vector<int> x, vector<int> y, const int& sz) {
  int tl = x.size() + y.size() - 1, lth = 1;
  while (lth < tl) lth <<= 1;
  x.resize(lth), y.resize(lth), NTT(x, 0), NTT(y, 0);
  for (int i = 0; i < lth; ++i) x[i] = 1ll * x[i] * y[i] % mod;
  NTT(x, 1), x.resize(sz);
  return x;
}
vector<int> Inv(vector<int> x) {
  if (x.size() == 1) return x[0] = POW(x[0], mod - 2), x;
  vector<int> tmp = x;
  int ts = x.size(), sz = (ts + 1 >> 1);
  tmp.resize(sz), tmp = Inv(tmp);
  int tl = ts + tmp.size() + tmp.size() - 2, lth = 1;
  while (lth < tl) lth <<= 1;
  x.resize(lth), tmp.resize(lth), NTT(x, 0), NTT(tmp, 0);
  for (int i = 0; i < lth; ++i)
    tmp[i] = (2 - 1ll * x[i] * tmp[i]) % mod * tmp[i] % mod,
    (tmp[i] += (tmp[i] >> 31) & mod);
  NTT(tmp, 1);
  return tmp.resize(ts), tmp;
}
vector<int> Ln(vector<int> x) {
  vector<int> tmp = x;
  for (int i = 1; i < tmp.size(); ++i) tmp[i - 1] = 1ll * i * tmp[i] % mod;
  tmp.pop_back(), tmp = Mul(tmp, Inv(x), x.size());
  for (int i = x.size() - 1; i > 0; --i)
    tmp[i] = 1ll * tmp[i - 1] * iv[i] % mod;
  tmp[0] = 0;
  return tmp;
}
vector<int> Exp(vector<int> x) {
  if (x.size() == 1) return x[0] = 1, x;
  int sz = (x.size() + 1 >> 1);
  vector<int> tmp = x, t2;
  tmp.resize(sz), tmp = Exp(tmp), t2 = tmp;
  t2.resize(x.size());
  return Mul(tmp, Plus(Minus(Poly(1), Ln(t2)), x), x.size());
}
vector<int> POW(vector<int> x, const int& y, const int& yc) {
  return Exp(Mul(Ln(x), y));
}
void init(const int& x) {
  lm = 1;
  while (lm < x) lm <<= 1;
  for (int i = 2; i <= lm; ++i)
    lg[i] = lg[i >> 1] + 1,
    lg[i] != lg[i - 1]                ? rt[i][0] = POW(3, (mod - 1) / i),
    rt[i][1] = POW(rt[i][0], mod - 2) : 0;
  iv[1] = 1;
  for (int i = 2; i <= lm; ++i)
    iv[i] = (-1ll * (mod / i) * iv[mod % i]) % mod + mod;
}
}  // namespace poly
using namespace poly;
int n, tmp, s[100010], V[100010], fac[100010], invf[100010], a0;
vector<int> m, m1, md, t1, t2, val1, val2, f, ff, v, v2, tv, mp, im;
int main() {
  scanf("%d", &n), poly::init((n + 10) * 3), t1.push_back(0), t1.push_back(1),
      t2 = t1, t2[0] = 1, t2.resize(n + 5);
  fac[0] = 1;
  for (int i = 1; i <= n + 5; ++i) fac[i] = 1ll * fac[i - 1] * i % mod;
  invf[n + 5] = POW(fac[n + 5], mod - 2);
  for (int i = n + 4; i >= 0; --i) invf[i] = 1ll * invf[i + 1] * (i + 1) % mod;
  m = Ln(t2);
  for (int i = 0; i < m.size() - 1; ++i) m[i] = m[i + 1];
  m.pop_back(), m = Inv(m), md.resize(m.size() - 1), m1.resize(m.size() - 1);
  for (int i = 0; i < m.size() - 1; ++i)
    md[i] = 1ll * m[i + 1] * (i + 1) % mod, m1[i] = m[i + 1];
  mp = POW(m, n + 1, n + 1), im = Inv(m1);
  val1 = Mul(Mul(md, mp, n + 2), Mul(im, im, n + 2), n + 2);
  val2 = Mul(mp, im, n + 2), tmp = POW(n + 1, mod - 2);
  for (int i = 0; i <= n + 1; ++i)
    val1[i] = 1ll * val1[i] * tmp % mod, val2[i] = 1ll * val2[i] * tmp % mod;
  for (int i = 0; i <= n; ++i)
    s[i] = (val1[i + 1] + (mod - 1ll) * (n - i + 1) % mod * val2[i + 1]) % mod;
  f.resize(n + 2);
  for (int i = 0; i < n + 2; ++i) f[i] = mod - invf[i + 2];
  f = Inv(f), v.resize(n + 1), v2.resize(n + 1);
  for (int i = 0; i <= n; ++i)
    (v[i] = f[i + 1] - s[i] - (!i)) >= mod ? v[i] -= mod
                                           : (v[i] < 0 ? v[i] += mod : 0),
        v[i] = 1ll * v[i] * fac[i] % mod;
  for (int i = 0; i <= n - i; ++i) swap(v[i], v[n - i]);
  for (int i = 0; i <= n; ++i)
    v2[i] = ((i & 1 ? mod - 1ll : 1ll) * invf[i]) % mod;
  tv = Mul(v, v2, n + 1);
  for (int i = 0; i <= n - i; ++i) swap(tv[i], tv[n - i]);
  for (int i = 1; i <= n; ++i) a0 = (a0 + 1ll * fac[n] * invf[i]) % mod;
  printf("%d", a0);
  for (int i = 1; i < n; ++i)
    printf(" %lld", 1ll * tv[i] * fac[n] % mod * invf[i] % mod);
  return 0;
}