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;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <class T>
using vv = vector<vector<T>>;
template <class T>
inline bool MX(T &l, const T &r) {
  return l < r ? l = r, 1 : 0;
}
template <class T>
inline bool MN(T &l, const T &r) {
  return l > r ? l = r, 1 : 0;
}
const ll MOD = 998244353;
ll modpow(ll r, ll n, ll m = MOD) {
  ll re = 1, d = r % m;
  if (n < 0) (n %= m - 1) += m - 1;
  for (; n; n /= 2) {
    if (n & 1) (re *= d) %= m;
    (d *= d) %= m;
  }
  return re;
}
template <int mod = MOD>
struct ModInt {
  int v;
  ModInt(int v = 0) : v(v) {}
  ModInt operator+(const ModInt &n) const {
    return v + n.v < mod ? v + n.v : v + n.v - mod;
  }
  ModInt operator-(const ModInt &n) const {
    return v - n.v < 0 ? v - n.v + mod : v - n.v;
  }
  ModInt operator*(const ModInt &n) const { return ll(v) * n.v % mod; }
  ModInt operator/(const ModInt &n) const {
    return ll(v) * modpow(n.v % mod, -1, mod) % mod;
  }
  ModInt operator+(const ll &n) const {
    return v + n < mod ? v + n : v + n - mod;
  }
  ModInt operator-(const ll &n) const {
    return v - n < 0 ? v - n + mod : v - n;
  }
  ModInt operator*(const ll &n) const { return ll(v) * (n % mod) % mod; }
  ModInt operator/(const ll &n) const {
    return ll(v) * modpow(n % mod, -1, mod) % mod;
  }
  ModInt &operator+=(const ModInt &n) {
    v += n.v;
    if (v >= mod) v -= mod;
    return *this;
  }
  ModInt &operator-=(const ModInt &n) {
    v -= n.v;
    if (v < 0) v += mod;
    return *this;
  }
  ModInt &operator*=(const ModInt &n) {
    v = ll(v) * n.v % mod;
    return *this;
  }
  ModInt &operator/=(const ModInt &n) {
    v = ll(v) * modpow(n.v, -1, mod) % mod;
    return *this;
  }
  ModInt &operator+=(const ll &n) {
    v += n;
    if (v >= mod) v -= mod;
    return *this;
  }
  ModInt &operator-=(const ll &n) {
    v -= n;
    if (v < 0) v += mod;
    return *this;
  }
  ModInt &operator*=(const ll &n) {
    v = ll(v) * n % mod;
    return *this;
  }
  ModInt &operator/=(const ll &n) {
    v = ll(v) * modpow(n, -1, mod) % mod;
    return *this;
  }
  bool operator==(const ModInt &n) const { return v == n.v; };
  bool operator!=(const ModInt &n) const { return v != n.v; };
  ModInt &operator++() { return operator+=(1); }
  ModInt &operator--() { return operator-=(1); }
  ModInt operator++(int i) {
    ModInt tmp(*this);
    operator++();
    return tmp;
  }
  ModInt operator--(int i) {
    ModInt tmp(*this);
    operator--();
    return tmp;
  }
};
template <int mod>
ostream &operator<<(ostream &os, const ModInt<mod> &n) {
  return os << n.v;
};
template <int mod>
ModInt<mod> operator+(const ll &n, const ModInt<mod> &m) {
  return m.v + n < mod ? m.v + n : m.v + n - mod;
}
template <int mod>
ModInt<mod> operator-(const ll &n, const ModInt<mod> &m) {
  return n - m.v < 0 ? n - m.v + mod : n - m.v;
}
template <int mod>
ModInt<mod> operator*(const ll &n, const ModInt<mod> &m) {
  return ll(m.v) * (n % mod) % mod;
}
template <int mod>
ModInt<mod> operator/(const ll &n, const ModInt<mod> &m) {
  return ModInt<mod>(n % mod) / m;
}
template <int mod>
ModInt<mod> modpow(ModInt<mod> r, ll n) {
  ModInt<mod> re(1);
  if (n < 0) (n %= mod - 1) += mod - 1;
  for (; n; n /= 2) {
    if (n & 1) re *= r;
    r *= r;
  }
  return re;
}
vector<ModInt<MOD>> fact, finv, inv;
ModInt<MOD> comb(ll n, ll r) {
  if (n < r || r < 0) return 0;
  return fact[n] * finv[n - r] * finv[r];
}
class Doralion {
  void Modinvs(vector<ModInt<MOD>> &re, int n) {
    re.resize(n + 1);
    re[1] = 1;
    for (int i = 2; i <= n; ++i) re[i] = re[MOD % i] * (MOD - MOD / i);
  }
  void Facts(vector<ModInt<MOD>> &re, int n) {
    re.resize(n + 1);
    re[0] = 1;
    for (int(i) = 0; (i) < (int)(n); ++(i)) re[i + 1] = re[i] * (i + 1);
  }
  void Factinvs(vector<ModInt<MOD>> &re, const vector<ModInt<MOD>> &inv,
                int n) {
    re.resize(n + 1);
    re[0] = 1;
    for (int(i) = 0; (i) < (int)(n); ++(i)) re[i + 1] = re[i] * inv[i + 1];
  }

 public:
  Doralion(int n) {
    Modinvs(inv, n);
    Facts(fact, n);
    Factinvs(finv, inv, n);
  }
} doralion(1123456);
void test(const int n) {
  vector<int> p(n);
  iota((p).begin(), (p).end(), 0);
  vector<int> re(n);
  do {
    int cnt = 0;
    for (int(i) = (int)(1); (i) < (int)(n); ++(i))
      if (p[i - 1] > p[i]) ++cnt;
    ++re[cnt];
  } while (next_permutation((p).begin(), (p).end()));
  ;
}
ModInt<MOD> dp[5123][5123];
ModInt<MOD> A(int n, int m) {
  ModInt<MOD> re = 0;
  for (int(k) = 0; (k) < (int)(m + 1); ++(k)) {
    ModInt<MOD> tmp = comb(n + 1, k) * modpow(m + 1 - k, n);
    if (k % 2)
      re -= tmp;
    else
      re += tmp;
  }
  return re;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(0);
  dp[0][0] = 1;
  for (int(n) = 0; (n) < (int)(5005); ++(n))
    for (int(m) = 0; (m) < (int)(5005); ++(m)) {
      if (n && m) dp[n][m] += dp[n - 1][m - 1] * (n - m);
      if (n) dp[n][m] += dp[n - 1][m] * (m + 1);
    }
  int n;
  cin >> n;
  vector<ModInt<MOD>> re(n);
  for (int(i) = 0; (i) < (int)(n); ++(i))
    for (int(j) = 0; (j) < (int)(n); ++(j)) {
      re[j] += dp[i + 1][j] * finv[i + 1];
    }
  for (int(i) = 0; (i) < (int)(n); ++(i)) cout << re[i] * fact[n] << " ";
  cout << "\n";
  return 0;
}