Problem: One day, Takahashi was given the following problem from Aoki:

* You are given a tree with N vertices and an integer K. The vertices are numbered 1 through N. The edges are represented by pairs of integers (a_i, b_i).
* For a set S of vertices in the tree, let f(S) be the minimum number of the vertices in a subtree of the given tree that contains all vertices in S.
* There are <image> ways to choose K vertices from the trees. For each of them, let S be the set of the chosen vertices, and find the sum of f(S) over all <image> ways.
* Since the answer may be extremely large, print it modulo 924844033(prime).



Since it was too easy for him, he decided to solve this problem for all K = 1,2,...,N.

Constraints

* 2 ≦ N ≦ 200,000
* 1 ≦ a_i, b_i ≦ N
* The given graph is a tree.

Input

The input is given from Standard Input in the following format:


N
a_1 b_1
a_2 b_2
:
a_{N-1} b_{N-1}


Output

Print N lines. The i-th line should contain the answer to the problem where K=i, modulo 924844033.

Examples

Input

3
1 2
2 3


Output

3
7
3


Input

4
1 2
1 3
1 4


Output

4
15
13
4


Input

7
1 2
2 3
2 4
4 5
4 6
6 7


Output

7
67
150
179
122
45
7

Solution (in JAVA):

Solution:
import java.io.*;
import java.lang.reflect.Array;
import java.math.*;
import java.text.DecimalFormat;
import java.util.*;




public class Main {
    private static final int mod = 924844033;
    private static int n;
    private static int [] fr,to,val,siz;
    private static ArrayList<Integer> [] E;
    private static int [] fact,rev;

    private static int add(int a,int b) {
        a += b;
        if (a >= mod) a -= mod;
        if (a < 0) a += mod;
        return a;
    }

    private static int mul(int a,int b) {
        return (int)((a*(long)b)%mod);
    }
    private static void init() throws Exception{
        fr = new int[n-1];
        to = new int[n-1];
        val = new int[n-1];
        siz = new int[n+1];
        E = new ArrayList[n+1];
        for (int u = 1;u <= n;u++)
            E[u] = new ArrayList<>();

        fact = new int[n+1];
        fact[0] = 1;
        for (int i = 1;i <= n;i++)
            fact[i] = mul(fact[i-1],i);

        int [] r = new int[n+1];
        rev = new int[n+1];
        rev[0] = rev[1] = r[1] = 1;
        for (int i = 2;i <= n;i++) {
            r[i] = add(mod ,-mul(mod/i, r[mod%i]));
            rev[i] = mul(rev[i-1],r[i]);
            if (mul(fact[i],rev[i]) != 1)
                throw new Exception("!= 1");
        }

    }

    private static int C(int n,int k) {
        if (k > n) return 0;
        int res = fact[n];
        res = mul(res,rev[k]);
        res = mul(res,rev[n-k]);
        return res;
    }


    private static void dfs(int u,int p){
        siz[u] = 1;
        for (int e : E[u]) {
            int v = fr[e] + to[e] - u;
            if (v == p) continue;
            fr[e] = u; to[e] = v;
            dfs(v,u);
            siz[u] += siz[v];
        }
    }

    public static void main(String[] args) throws Exception {
        IO io = new IO(null, null);
        n = io.getNextInt();
        init();
        for (int e = 0;e < n-1;e++) {
            int a = io.getNextInt(),b = io.getNextInt();
            fr[e] = a;
            to[e] = b;
            E[a].add(e);
            E[b].add(e);
        }
        dfs(1,0);

        int [] b = new int[n+1];
        for (int e = 0;e < n-1;e++) {
            int v = to[e];
            b[siz[v]] = add(b[siz[v]],-1);
            b[n-siz[v]] = add(b[n-siz[v]],-1);
        }
        b[n] = n;

        int [] c = new int[n+1];
        for (int i = 0;i <= n;i++)
            c[i] = mul(fact[i],b[i]);

        int [] d = new int[n+1];
        for (int i = 0;i <= n;i++)
            d[i] = rev[n-i];


        int [] R = NTT.mult(c,d,mod,2187);


        for (int i = 1;i <= n;i++)
            io.println(mul(R[i+n],rev[i]));


        io.close();
    }
}



class NTT{
    private static int add(int a,int b,int mod) {
        a %= mod;
        b %= mod;
        a += b;
        if (a >= mod) a -= mod;
        if (a < 0) a += mod;
        return a;
    }

    private static int mul(int a,int b,int mod) {
        a %= mod; b %= mod;
        return (int)((a*(long)b)%mod);
    }
    public static int [] mult(int [] fA,int [] fB,int P,int g) {
        int n = Math.max(fA.length,fB.length);
        while (n != (n & -n)) n++;
        n <<= 1;
        n = 1048576;

        int [] pA = new int[n];
        int [] pB = new int[n];
        int [] pC = new int[n];
        for (int i = 0;i < fA.length;i++) pA[i] = fA[i];
        for (int i = 0;i < fB.length;i++) pB[i] = fB[i];

        pA = ntt(pA,false,g,P);
        pB = ntt(pB,false,g,P);

        for (int i = 0;i < n;i++)
            pC[i] = mul(pA[i],pB[i],P);
        return ntt(pC,true,g,P);
    }
    private static int getLen(int n) {
        if (n == 0) return 1;
        int r = 0;
        while (n > 0) {
            r ++;
            n /= 2;
        }
        return r;
    }
    private static int rev(int n,int l){
        int r = 0;
        for (int i = 0;i < l;i++){
            r = (r << 1) | (n & 1);
            n >>= 1;
        }
        return r;
    }

    private static void bit_rev(int [] IN,int [] OUT,int m) {
        int l = getLen(m) - 1;
        for (int i = 0; i < m; i++) {
            OUT[rev(i, l)] = IN[i];
        }
    }

    private static int powmod(int x,int p,int mod) {
        if (p == 0) return 1;
        int y = 1;
        for (;p > 1;p >>= 1) {
            if (p%2 == 1) y = mul(x,y,mod);
            x = mul(x,x,mod);
        }
        return mul(x,y,mod);
    }
    private static int [] ntt(int [] f,boolean inv,int g,int P) {
        if (f.length == 1) return f;
        int n = f.length;
        int [] O = new int[n];
        bit_rev(f,O,n);
        for(int m = 2;m <= n;m <<= 1){
            int gk = powmod(g,n/m,P);
            if (inv) gk = powmod(gk,P-2,P);

//            System.err.println(m + ":");
            for(int k = 0;k < n;k += m){
                int w = 1;
                for(int j = 0;j < m/2;j++){
                    int t = mul(w,O[k + j + m/2],P);
                    int u = O[k + j];
                    O[k + j] = add(u,t,P);
                    O[k + j + m/2] = add(u,P-t,P);
//                    if (O[k + j] != 0) System.err.println(O[k + j]);
//                    if (O[k + j + m/2] != 0) System.err.println(O[k + j + m/2]);;
                    w = mul(w,gk,P);
                }
            }
        }
        if(inv) {
            int in = powmod(n,P-2,P);
            for(int i = 0;i < n;i++) O[i] = mul(O[i],in,P);
        }
        return O;
    }
}



class IO{
    private BufferedReader br;
    private StringTokenizer st;
    private PrintWriter writer;
    private String inputFile,outputFile;

    public boolean hasMore() throws IOException{
        if(st != null && st.hasMoreTokens()) return true;
        if(br != null && br.ready()) return true;
        return false;
    }
    public String getNext() throws FileNotFoundException, IOException{
        while(st == null || !st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
        return st.nextToken();
    }

    public String getNextLine() throws FileNotFoundException, IOException{
        return br.readLine().trim();
    }

    public int getNextInt() throws FileNotFoundException, IOException{
        return Integer.parseInt(getNext());
    }
    public long getNextLong() throws FileNotFoundException, IOException{
        return Long.parseLong(getNext());
    }

    public void print(double x,int num_digits) throws  IOException{
        writer.printf("%." + num_digits + "f" ,x);
    }
    public void println(double x,int num_digits) throws  IOException{
        writer.printf("%." + num_digits + "f\n" ,x);
    }
    public void print(Object o) throws  IOException{
        writer.print(o.toString());
    }

    public void println(Object o) throws  IOException{
        writer.println(o.toString());
    }
    public IO(String x,String y) throws FileNotFoundException, IOException{
        inputFile = x;
        outputFile = y;
        if(x != null) br = new BufferedReader(new FileReader(inputFile));
        else br = new BufferedReader(new InputStreamReader(System.in));
        if(y != null) writer = new PrintWriter(new BufferedWriter(new FileWriter(outputFile)));
        else writer = new PrintWriter(new OutputStreamWriter(System.out));
    }

    protected void close() throws IOException{
        br.close();
        writer.close();
    }
    public void outputArr(Object [] A) throws IOException{
        int L = A.length;
        for (int i = 0;i < L;i++) {
            if(i > 0) writer.print(" ");
            writer.print(A[i]);
        }
        writer.print("\n");
    }
}