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 JAVA):

Solution:

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.text.DecimalFormat;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Random;
import java.util.StringTokenizer;

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
/**
 *
 * @author Andy Phan
 */
public class f {

    public static void main(String[] args) {
        FS in;
        PrintWriter out;
        
        try {
            in = new FS(new FileInputStream("substring.in"));
            out = new PrintWriter(new File("substring.out"));
        } catch(Exception e) {
            in = new FS(System.in);
            out = new PrintWriter(System.out);
        }
        new f().solve(in, out);
        
        out.close();
    }
    
    long MOD = 998244353;
    
    
    long pow(long a, long b) {
        long ret = 1;
        for(; b > 0; b >>= 1, a = (a*a)%MOD) if((b&1) == 1) ret = (ret*a)%MOD;
        return ret;
    }

    public void solve(FS in, PrintWriter out) {
        int n = in.nextInt();
        long[][] d = new long[5005][5005];
        long[] fac = new long[5005], inv = new long[5005], ans = new long[5005];
        d[0][0] = fac[0]=inv[0] = 1;
        for(int i = 1; i <= n; i++) fac[i] = (fac[i-1]*i)%MOD;
        inv[n] = pow(fac[n], MOD-2);
        for(int i = n-1; i >= 1; i--) inv[i] = (inv[i+1]*(i+1))%MOD;
        for(int i = 1; i <= n; i++) for(int j=  1; j <= i; j++) d[i][j] = (d[i-1][j-1]*(i-j+1)+d[i-1][j]*j)%MOD;
        for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) ans[i] = (ans[i]+d[j][i]*inv[j])%MOD;
        for(int i = 1; i <= n; i++) out.printf("%d ", (ans[i]*fac[n])%MOD);
        out.println();
    }

    static class FS {

        BufferedReader in;
        StringTokenizer token;

        public FS(InputStream str) {
            in = new BufferedReader(new InputStreamReader(str));
        }

        public String next() {
            if (token == null || !token.hasMoreElements()) {
                try {
                    token = new StringTokenizer(in.readLine());
                } catch (IOException ex) {
                }
                return next();
            }
            return token.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }
    }
}