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>
inline int getint() {
  int x = 0, p = 1;
  char c = getchar();
  while (c <= 32) c = getchar();
  if (c == 45) p = -p, c = getchar();
  while (c > 32) x = x * 10 + c - 48, c = getchar();
  return x * p;
}
using namespace std;
const int mod = 998244353;
inline void reduce(int &x) { x += x >> 31 & mod; }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
const int N = 5005;
int n, fac[N], inv[N], s[N][N], h[N];
int modpow(int x, int y) {
  int ans = 1;
  while (y) {
    if (y & 1) ans = mul(ans, x);
    x = mul(x, x);
    y >>= 1;
  }
  return ans;
}
int modinv(int x) { return modpow(x, mod - 2); }
int c(int x, int y) {
  if (y > x || y < 0) return 0;
  return mul(fac[x], mul(inv[y], inv[x - y]));
}
int main() {
  n = getint();
  fac[0] = 1;
  for (int i = 1; i < N; i++) fac[i] = mul(fac[i - 1], i);
  inv[N - 1] = modinv(fac[N - 1]);
  for (int i = N - 2; i >= 0; i--) inv[i] = mul(inv[i + 1], i + 1);
  s[0][0] = s[1][1] = 1;
  for (int i = 2; i < N; i++) {
    for (int j = 1; j <= i; j++) {
      reduce(s[i][j] = s[i - 1][j - 1] + mul(s[i - 1][j], j) - mod);
    }
  }
  for (int k = 1; k <= n; k++) {
    for (int j = k; j <= n; j++) {
      reduce(h[k] += mul(inv[j], mul(fac[j - k + 1], s[j][j - k + 1])) - mod);
    }
  }
  for (int i = 1; i <= n; i++) {
    int res = 0;
    for (int k = i; k <= n; k++) {
      if (k - i & 1)
        reduce(res -= mul(c(k - 1, i - 1), h[k]));
      else
        reduce(res += mul(c(k - 1, i - 1), h[k]) - mod);
    }
    printf("%d ", mul(fac[n], res));
  }
  return 0;
}