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 <typename T>
inline void read(T &f) {
  f = 0;
  T fu = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') {
      fu = -1;
    }
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    f = (f << 3) + (f << 1) + (c & 15);
    c = getchar();
  }
  f *= fu;
}
template <typename T>
void print(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x < 10)
    putchar(x + 48);
  else
    print(x / 10), putchar(x % 10 + 48);
}
template <typename T>
void print(T x, char t) {
  print(x);
  putchar(t);
}
const int md = 998244353;
inline int add(int x, int y) {
  if (x + y >= md) return x + y - md;
  return x + y;
}
inline void addx(int &x, int y) {
  x += y;
  if (x >= md) x -= md;
}
inline int sub(int x, int y) {
  if (x < y) return x - y + md;
  return x - y;
}
inline void subx(int &x, int y) {
  x -= y;
  if (x < 0) x += md;
}
inline int mul(int x, int y) { return 1ull * x * y % md; }
inline int fpow(int x, int y) {
  int ans = 1;
  while (y) {
    if (y & 1) ans = mul(ans, x);
    y >>= 1;
    x = mul(x, x);
  }
  return ans;
}
const int N = 5005;
int f[N][N], fac[N], inv[N];
int n;
inline int C(int n, int m) {
  if (m < 0 || n < m) return 0;
  return mul(fac[n], mul(inv[m], inv[n - m]));
}
int main() {
  read(n);
  fac[0] = 1;
  for (int i = 1; i <= n; i++) fac[i] = mul(fac[i - 1], i);
  inv[n] = fpow(fac[n], md - 2);
  for (int i = n; i >= 1; i--) inv[i - 1] = mul(inv[i], i);
  f[0][0] = 1;
  for (int i = 1; i <= n; i++) {
    f[i][0] = 1;
    for (int j = 1; j < i; j++)
      f[i][j] = add(mul(f[i - 1][j - 1], i - j), mul(f[i - 1][j], j + 1));
  }
  for (int i = 1; i <= n; i++) {
    int ans = 0;
    for (int j = i; j <= n; j++) {
      ans = add(ans, mul(f[j][i - 1], mul(C(n, j), fac[n - j])));
    }
    print(ans, i == n ? '\n' : ' ');
  }
  return 0;
}