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>
struct MI {
 private:
  char bb[4096];
  FILE* f;
  char *bs, *be;
  char e;
  bool o, l;

 public:
  MI() : MI(stdin) {}
  MI(FILE* f) : f(f), bs(0), be(0), o(0), l(0) {}
  inline char get() {
    if (o) {
      o = 0;
      return e;
    }
    if (bs == be) be = (bs = bb) + fread(bb, 1, sizeof(bb), f);
    if (bs == be) {
      l = 1;
      return -1;
    };
    return *bs++;
  }
  inline void unget(char c) {
    o = 1;
    e = c;
  }
  template <class T>
  inline MI& operator>(T&);
};
template <class T>
struct Q {
  const static bool U = T(-1) >= T(0);
  inline void operator()(MI& t, T& r) const {
    r = 0;
    char c;
    bool y = 0;
    if (U)
      for (;;) {
        c = t.get();
        if (c == -1) goto E;
        if (isdigit(c)) break;
      }
    else
      for (;;) {
        c = t.get();
        if (c == -1) goto E;
        if (c == '-') {
          c = t.get();
          if (isdigit(c)) {
            y = 1;
            break;
          };
        } else if (isdigit(c))
          break;
        ;
      };
    for (;;) {
      if (c == -1) goto E;
      if (isdigit(c))
        r = r * 10 + (c ^ 48);
      else
        break;
      c = t.get();
    }
    t.unget(c);
  E:;
    if (y) r = -r;
  }
};
template <>
struct Q<char> {};
template <class T>
inline MI& MI::operator>(T& t) {
  Q<T>()(*this, t);
  return *this;
}
template <class T>
inline std::ostream& operator<(std::ostream& out, const T& t) {
  return out << t;
}
using std::cout;
MI cin;
const int $n = 5005;
const int mod = 998244353;
inline void Add(int& x, int y) {
  if ((x += y) >= mod) x -= mod;
}
inline long long ksm(long long x, int p = mod - 2) {
  long long ret = 1;
  for (; p; p >>= 1, (x *= x) %= mod)
    if (p & 1) (ret *= x) %= mod;
  return ret;
}
int n, fac[$n], ifac[$n], e[$n][$n];
inline void init(int n) {
  for (int i = fac[0] = ifac[0] = 1; i <= n; ++i)
    fac[i] = (long long)fac[i - 1] * i % mod;
  ifac[n] = ksm(fac[n]);
  for (int i = n; i > 1; --i) ifac[i - 1] = (long long)ifac[i] * i % mod;
}
int main() {
  cin > n;
  init(n);
  e[0][0] = 1;
  for (int i = 1; i <= n; ++i) {
    e[i][0] = 1;
    for (int j = 1; j <= i; ++j)
      e[i][j] = ((long long)e[i - 1][j] * (j + 1) +
                 (long long)e[i - 1][j - 1] * (i - j)) %
                mod;
  }
  for (int i = 0; i < n; ++i) {
    int ans = 0;
    for (int j = i + !i; j <= n; ++j)
      Add(ans, (long long)e[j][i] * ifac[j] % mod);
    cout < ((long long)ans * fac[n] % mod) < " \n"[i == n - 1];
  }
}