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>
#pragma GCC optimize("Ofast,inline,unroll-loops,fast-math")
using namespace std;
namespace Comb {
int f[5020], g[5020];
int Power(int x, int y) {
  int o;
  for (o = 1; y; y >>= 1) {
    if (y & 1) o = (long long)o * x % 998244353;
    x = (long long)x * x % 998244353;
  }
  return o;
}
void InitComb(void) {
  int i;
  for (i = f[0] = 1; i < 5020; i++) f[i] = (long long)f[i - 1] * i % 998244353;
  g[5020 - 1] = Power(f[5020 - 1], 998244353 - 2);
  for (i = 5020 - 2; i > -1; i--)
    g[i] = (long long)g[i + 1] * (i + 1) % 998244353;
  return;
}
}  // namespace Comb
int f[5020][5020], g[5020];
inline int D(int n, int m) {
  return (long long)f[n + 1][n + 1 - m] * Comb::g[n + 1] % 998244353;
}
int main(void) {
  int n;
  int i, j, o;
  Comb::InitComb();
  scanf("%d", &n);
  f[0][0] = 1;
  for (i = 1; i <= n; i++)
    for (j = 1; j <= i; j++)
      f[i][j] = ((long long)f[i - 1][j] + f[i - 1][j - 1]) * j % 998244353;
  for (i = 0; i < n; i++)
    for (j = i; j < n; j++) g[i] = (g[i] + D(j, i)) % 998244353;
  for (i = 0; i < n; i++) {
    for (j = i, o = 0; j < n; j++)
      o = (o + (long long)((j - i) & 1 ? 998244353 - 1 : 1) * Comb::f[j] %
                   998244353 * Comb::g[j - i] % 998244353 * g[j] % 998244353) %
          998244353;
    o = (long long)o * Comb::f[n] % 998244353 * Comb::g[i] % 998244353;
    printf("%d%c", o, " \n"[i == n - 1]);
  }
  return 0;
}