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 std::max;
using std::min;
const int inf = 0x3f3f3f3f, Inf = 0x7fffffff;
const long long INF = 0x3f3f3f3f3f3f3f3f;
std::mt19937 rnd(std::chrono::steady_clock::now().time_since_epoch().count());
template <typename _Tp>
_Tp gcd(const _Tp &a, const _Tp &b) {
  return (!b) ? a : gcd(b, a % b);
}
template <typename _Tp>
inline _Tp abs(const _Tp &a) {
  return a >= 0 ? a : -a;
}
template <typename _Tp>
inline void chmax(_Tp &a, const _Tp &b) {
  (a < b) && (a = b);
}
template <typename _Tp>
inline void chmin(_Tp &a, const _Tp &b) {
  (b < a) && (a = b);
}
template <typename _Tp>
inline void read(_Tp &x) {
  char ch(getchar());
  bool f(false);
  while (!isdigit(ch)) f |= ch == 45, ch = getchar();
  x = ch & 15, ch = getchar();
  while (isdigit(ch)) x = (((x << 2) + x) << 1) + (ch & 15), ch = getchar();
  f && (x = -x);
}
template <typename _Tp, typename... Args>
inline void read(_Tp &t, Args &...args) {
  read(t);
  read(args...);
}
inline int read_str(char *s) {
  char ch(getchar());
  while (ch == ' ' || ch == '\r' || ch == '\n') ch = getchar();
  char *tar = s;
  *tar++ = ch, ch = getchar();
  while (ch != ' ' && ch != '\r' && ch != '\n' && ch != EOF)
    *tar++ = ch, ch = getchar();
  return *tar = 0, tar - s;
}
const int max_len = 1 << 18;
const int N = max_len + 9;
const int mod = 998244353;
int _inv_[N];
template <typename _Tp1, typename _Tp2>
inline void add(_Tp1 &a, _Tp2 b) {
  (a += b) >= mod && (a -= mod);
}
template <typename _Tp1, typename _Tp2>
inline void sub(_Tp1 &a, _Tp2 b) {
  (a -= b) < 0 && (a += mod);
}
template <typename _Tp>
inline _Tp _sub(_Tp a, const _Tp &b) {
  (a += mod - b) >= mod && (a -= mod);
  return a;
}
long long ksm(long long a, long long b = mod - 2) {
  long long res = 1;
  while (b) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod, b >>= 1;
  }
  return res;
}
void print(const std::vector<int> &a) {
  for (auto it : a) printf("%d ", it);
  printf("\n");
}
std::vector<int> operator<<(const std::vector<int> &a, unsigned int b) {
  std::vector<int> o(a.size() + b);
  for (unsigned int i = 0; i < b; ++i) o[i] = 0;
  for (unsigned int i = 0; i < a.size(); ++i) o[i + b] = a[i];
  return o;
}
inline std::vector<int> operator<<=(std::vector<int> &a, unsigned int b) {
  return a = a << b;
}
inline std::vector<int> operator>>(const std::vector<int> &a, unsigned int b) {
  return b >= a.size() ? std::vector<int>()
                       : std::vector<int>{a.begin() + b, a.end()};
}
inline std::vector<int> operator>>=(std::vector<int> &a, unsigned int b) {
  return a = b >= a.size() ? std::vector<int>()
                           : std::vector<int>{a.begin() + b, a.end()};
}
std::vector<int> operator+=(std::vector<int> &a, const std::vector<int> &b) {
  if (((int)b.size()) > ((int)a.size())) a.resize(((int)b.size()));
  for (unsigned int i = 0; i < b.size(); ++i) add(a[i], b[i]);
  return a;
}
inline std::vector<int> operator+(const std::vector<int> &a,
                                  const std::vector<int> &b) {
  std::vector<int> tmp(a);
  tmp += b;
  return tmp;
}
std::vector<int> operator-=(std::vector<int> &a, const std::vector<int> &b) {
  if (((int)b.size()) > ((int)a.size())) a.resize(((int)b.size()));
  for (unsigned int i = 0; i < b.size(); ++i) sub(a[i], b[i]);
  return a;
}
inline std::vector<int> operator-(const std::vector<int> &a,
                                  const std::vector<int> &b) {
  std::vector<int> tmp(a);
  tmp -= b;
  return tmp;
}
int Omgs[N], r[N];
const long long G = ksm(3, (mod - 1) / max_len);
int calc(int len) {
  int limit = 1;
  while (limit < len) limit <<= 1;
  for (int i = 0; i < limit; ++i)
    r[i] = (r[i >> 1] >> 1) | ((i & 1) ? (limit >> 1) : 0);
  return limit;
}
void setup() {
  _inv_[0] = _inv_[1] = 1;
  for (int i = 2; i < N; ++i)
    _inv_[i] = 1ll * _inv_[mod % i] * (mod - mod / i) % mod;
  Omgs[max_len >> 1] = 1;
  for (int i = (max_len >> 1) + 1; i < max_len; ++i)
    Omgs[i] = 1LL * Omgs[i - 1] * G % mod;
  for (int i = (max_len >> 1) - 1; i >= 0; --i) Omgs[i] = Omgs[i << 1];
}
void dft(std::vector<int> &a, int limit) {
  static int A[N];
  for (int i = 0; i < limit; ++i) A[r[i]] = a[i];
  for (int len = 2, hf = 1; len <= limit; len <<= 1, hf <<= 1)
    for (int pos = 0; pos < limit; pos += len) {
      int *w(Omgs + hf), *p(A + pos), *q(A + pos + hf);
      for (int i = 0; i < hf; ++i, ++p, ++q) {
        int tmp = 1LL * (*w++) * (*q) % mod;
        *q = _sub(*p, tmp), add(*p, tmp);
      }
    }
  for (int i = 0; i < limit; ++i) a[i] = A[i] % mod;
}
void idft(std::vector<int> &a, int limit) {
  std::reverse(&a[1], &a[limit]);
  dft(a, limit);
  unsigned long long inv = mod - (mod - 1) / limit;
  for (int i = 0; i < limit; ++i) a[i] = inv * a[i] % mod;
}
std::vector<int> operator*(std::vector<int> a, std::vector<int> b) {
  if (a.size() <= 40u || b.size() <= 40u) {
    std::vector<int> c(((int)a.size()) + ((int)b.size()) - 1);
    for (unsigned int i = 0; i < a.size(); ++i)
      for (unsigned int j = 0; j < b.size(); ++j)
        add(c[i + j], 1ull * a[i] * b[j] % mod);
    return c;
  }
  int tmp = ((int)a.size()) + ((int)b.size()), limit = calc(tmp);
  a.resize(limit), b.resize(limit), dft(a, limit), dft(b, limit);
  for (int i = 0; i < limit; ++i) a[i] = 1ull * a[i] * b[i] % mod;
  return idft(a, limit), a.resize(tmp - 1), a;
}
std::vector<int> sqr(std::vector<int> a) {
  if (a.size() <= 40u) {
    std::vector<int> c(((int)a.size()) + ((int)a.size()) - 1);
    for (unsigned int i = 0; i < a.size(); ++i)
      for (unsigned int j = 0; j < a.size(); ++j)
        add(c[i + j], 1ull * a[i] * a[j] % mod);
    return c;
  }
  int tmp = ((int)a.size()) << 1, limit = calc(tmp);
  a.resize(limit), dft(a, limit);
  for (int i = 0; i < limit; ++i) a[i] = 1ull * a[i] * a[i] % mod;
  return idft(a, limit), a.resize(tmp - 1), a;
}
inline std::vector<int> operator*=(std::vector<int> &a,
                                   const std::vector<int> &b) {
  return a = a * b;
}
template <typename _Tp>
inline std::vector<int> operator*=(std::vector<int> &a, const _Tp &b) {
  for (auto &&it : a) it = 1ll * it * b % mod;
  return a;
}
template <typename _Tp>
inline std::vector<int> operator*(std::vector<int> a, const _Tp &b) {
  return a *= b;
}
template <typename _Tp>
inline std::vector<int> operator*(const _Tp &b, std::vector<int> a) {
  return a *= b;
}
template <typename _Tp>
inline std::vector<int> operator/=(std::vector<int> &a, const _Tp &b) {
  long long inv = ksm(b);
  for (auto &&it : a) it = 1ll * it * inv % mod;
  return a;
}
template <typename _Tp>
inline std::vector<int> operator/(std::vector<int> a, const _Tp &b) {
  return a /= b;
}
template <typename _Tp>
inline std::vector<int> operator/(const _Tp &b, std::vector<int> a) {
  return a /= b;
}
std::vector<int> _inv(const std::vector<int> &F) {
  int len = ((int)F.size());
  if (len == 1) return {(int)ksm(F[0])};
  std::vector<int> H(_inv({F.begin(), F.begin() + (len >> 1)})), tmp(F * H),
      ans(H);
  tmp = std::vector<int>{tmp.begin() + (len >> 1), tmp.end()} * H;
  ans.resize(len);
  for (int i = 0; i < len >> 1; ++i)
    tmp[i] && (ans[(len >> 1) + i] = mod - tmp[i]);
  return ans;
}
std::vector<int> Inv(std::vector<int> F) {
  int tmp = ((int)F.size()), L = 1;
  for (; L < tmp; L <<= 1)
    ;
  F.resize(L);
  std::vector<int> ans(_inv(F));
  return ans.resize(tmp), ans;
}
std::pair<std::vector<int>, std::vector<int> > divide(
    const std::vector<int> &f, const std::vector<int> &g) {
  int n = ((int)f.size()), m = ((int)g.size());
  std::vector<int> F(f), G(g);
  std::reverse(F.begin(), F.end()), F.resize(n - m + 1);
  std::reverse(G.begin(), G.end()), G.resize(n - m + 1);
  std::vector<int> Q(F * Inv(G));
  Q.resize(n - m + 1), std::reverse(Q.begin(), Q.end());
  std::vector<int> R(f - Q * g);
  return R.resize(m - 1), std::make_pair(Q, R);
}
inline std::vector<int> Mod(const std::vector<int> &f,
                            const std::vector<int> &g) {
  return divide(f, g).second;
}
std::vector<int> _sqrt(const std::vector<int> &F) {
  int len = ((int)F.size());
  if (len == 1) return {1};
  std::vector<int> H(_sqrt({F.begin(), F.begin() + (len >> 1)}));
  H.resize(len);
  return (H + F * _inv(H)) / 2;
}
std::vector<int> Sqrt(std::vector<int> F) {
  int tmp = ((int)F.size()), L = 1;
  for (; L < tmp; L <<= 1)
    ;
  F.resize(L);
  std::vector<int> ans(_sqrt(F));
  return ans.resize(tmp), ans;
}
std::vector<int> deri(std::vector<int> a) {
  for (int i = 0; i + 1 < ((int)a.size()); ++i)
    a[i] = 1ll * (i + 1) * a[i + 1] % mod;
  return a.pop_back(), a;
}
std::vector<int> inte(std::vector<int> a) {
  a.resize(((int)a.size()) + 1);
  for (int i = ((int)a.size()) - 1; i >= 1; --i)
    a[i] = 1ll * a[i - 1] * _inv_[i] % mod;
  return a[0] = 0, a;
}
std::vector<int> Ln(std::vector<int> F) {
  std::vector<int> ans(inte(deri(F) * Inv(F)));
  return ans.resize(((int)F.size())), ans;
}
std::vector<int> _exp(const std::vector<int> &F) {
  int len = ((int)F.size());
  if (len == 1) return {1};
  std::vector<int> H(_exp({F.begin(), F.begin() + (len >> 1)}));
  H.resize(len);
  std::vector<int> ans(F - Ln(H));
  add(ans[0], 1);
  H.resize(len >> 1);
  return ans *= H, ans.resize(len), ans;
}
std::vector<int> Exp(std::vector<int> F) {
  int tmp = ((int)F.size()), L = 1;
  for (; L < tmp; L <<= 1)
    ;
  F.resize(L);
  std::vector<int> ans(_exp(F));
  return ans.resize(tmp), ans;
}
std::vector<int> ksm(std::vector<int> a, int b) {
  a = Ln(a);
  for (auto &&it : a) it = 1ll * it * b % mod;
  return Exp(a);
}
long long fac[N], inv[N], ifac[N];
int main() {
  setup();
  fac[0] = fac[1] = inv[0] = inv[1] = ifac[0] = ifac[1] = 1;
  for (int i = 2; i < N; ++i)
    fac[i] = fac[i - 1] * i % mod,
    inv[i] = inv[mod % i] * (mod - mod / i) % mod,
    ifac[i] = ifac[i - 1] * inv[i] % mod;
  int n;
  read(n);
  std::vector<int> H(n + 5);
  for (int i = 0; i < n + 5; ++i) H[i] = i & 1 ? mod - inv[i + 1] : inv[i + 1];
  H = Inv(H);
  std::vector<int> tp(Inv((std::vector<int>{1} - H) >> 1)), tmp(ksm(H, n + 1)),
      B(tmp * tp);
  B.resize(n + 5);
  std::vector<int> A(deri(H) * B);
  A.resize(n + 5), A *= tp, A.resize(n + 5);
  std::vector<int> C(n + 5);
  for (int i = 0; i <= n; ++i)
    C[i] = 1LL * inv[n + 1] *
           ((A[i + 1] + 1LL * B[i + 1] * (n - i + 1)) % mod) % mod;
  std::vector<int> D(n + 5);
  for (int i = 2; i < n + 5; ++i) D[i - 2] = mod - ifac[i];
  D = Inv(D) >> 1;
  std::vector<int> F(D - C);
  sub(F[0], 1), F.resize(n + 1);
  for (int i = 0; i < ((int)F.size()); ++i) F[i] = fac[i] * F[i] % mod;
  std::vector<int> G(n + 5);
  for (int i = 0; i <= n; ++i) G[n - i] = i & 1 ? mod - ifac[i] : ifac[i];
  F *= G;
  for (int i = 0; i < n; ++i)
    printf("%lld%c", 1LL * fac[n] * ifac[i] % mod * F[i + n] % mod,
           " \n"[i == n]);
  return 0;
}