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 <int mod>
struct modulo {
  int w;
  operator int() const { return w; }
  modulo() {}
  modulo(int w) {
    this->w = w;
    fix();
  }
  template <class type>
  modulo(type w) {
    this->w = w % mod;
    fix();
  }
  void inline fix() {
    if (w >= mod || w < -mod) w %= mod;
    if (w < 0) w += mod;
  }
  inline modulo operator-() const { return mod - w; }
  inline modulo &operator+=(const modulo &b) {
    if ((w += b.w) >= mod) w -= mod;
    return *this;
  }
  inline modulo &operator-=(const modulo &b) {
    if ((w -= b.w) < 0) w += mod;
    return *this;
  }
  inline modulo &operator*=(const modulo &b) {
    w = (unsigned long long)w * b.w % mod;
    return *this;
  }
  inline modulo &operator/=(const modulo &b) { return *this *= inv(b); }
  friend modulo operator+(const modulo &a, const modulo &b) {
    return modulo(a) += b;
  }
  template <class type>
  friend modulo operator+(const modulo &a, const type &b) {
    return modulo(a) += b;
  }
  template <class type>
  friend modulo operator+(const type &a, const modulo &b) {
    return modulo(a) += b;
  }
  friend modulo operator-(const modulo &a, const modulo &b) {
    return modulo(a) -= b;
  }
  template <class type>
  friend modulo operator-(const modulo &a, const type &b) {
    return modulo(a) -= b;
  }
  template <class type>
  friend modulo operator-(const type &a, const modulo &b) {
    return modulo(a) -= b;
  }
  friend modulo operator*(const modulo &a, const modulo &b) {
    return modulo(a) *= b;
  }
  template <class type>
  friend modulo operator*(const modulo &a, const type &b) {
    return modulo(a) *= b;
  }
  template <class type>
  friend modulo operator*(const type &a, const modulo &b) {
    return modulo(a) *= b;
  }
  friend modulo operator/(const modulo &a, const modulo &b) {
    return modulo(a) /= b;
  }
  template <class type>
  friend modulo operator/(const modulo &a, const type &b) {
    return modulo(a) /= b;
  }
  template <class type>
  friend modulo operator/(const type &a, const modulo &b) {
    return modulo(a) /= b;
  }
  friend inline modulo inv(const modulo &w) {
    int a = w, m = mod, u = 0, v = 1, t;
    for (; a != 0; t = m / a, m -= t * a, swap(a, m), u -= t * v, swap(u, v))
      ;
    return u;
  }
  friend inline modulo pow(const modulo &w, int p) {
    if (!w) return 0;
    modulo a = w, r = 1;
    for (; p > 0; a *= a, p >>= 1)
      if (p & 1) r *= a;
    return r;
  }
};
const int mod = 998244353;
const int nsz = 5e3;
int n;
modulo<mod> f[2][nsz + 5], g[nsz + 5], S[nsz + 5][nsz + 5], ans[nsz + 5];
modulo<mod> inline C(int n, int m) { return f[0][n] * f[1][m] * f[1][n - m]; }
void inline init() {
  f[0][0] = 1;
  for (int i = 1; i <= n; ++i) f[0][i] = f[0][i - 1] * i;
  f[1][n] = 1 / f[0][n];
  for (int i = n; i >= 1; --i) f[1][i - 1] = f[1][i] * i;
  S[0][0] = 1;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= i; ++j) S[i][j] = S[i - 1][j] * j + S[i - 1][j - 1];
  }
  for (int i = 0; i <= n; ++i) {
    for (int len = i + 1; len <= n; ++len)
      g[i] += f[0][len - i] * f[1][len] * S[len][len - i];
  }
}
void inline solve() {
  for (int k = 0; k < n; ++k) {
    for (int i = k; i <= n; ++i) {
      modulo<mod> res = g[i] * C(i, k) * f[0][n];
      ans[k + 1] += (i - k) & 1 ? -res : res;
    }
  }
}
int main() {
  scanf("%d", &n);
  init();
  solve();
  for (int k = 1; k <= n; ++k) printf("%d%c", ans[k].w, "\n "[k < n]);
}