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

Solution:
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #define LL long long
    using namespace std;
    const LL p=924844033,yg=5;
    LL n;
    struct node{
    	LL y,next;
    }a[400010];LL len=0,last[200010];
    LL f[200010],inv[200010],A[800010],B[800010],bin[800010];
    void ins(LL x,LL y)
    {
    	a[++len].y=y;
    	a[len].next=last[x];last[x]=len;
    }
    void pre()
    {
        f[0]=f[1]=inv[0]=inv[1]=1;
        for(LL i=2;i<=200000;i++) f[i]=f[i-1]*i%p,inv[i]=(p-p/i)*inv[p%i]%p;
        for(LL i=2;i<=200000;i++) inv[i]=inv[i-1]*inv[i]%p;
    }
    LL pow(LL a,LL b)
    {
    	LL ans=1;
    	while(b)
    	{
    		if(b&1) ans=ans*a%p;
    		a=a*a%p;b>>=1;
    	}
    	return ans;
    }
    LL size[200010];
    void ntt(LL *a,LL n,LL op)
    {
        for(LL i=0;i<n;i++) bin[i]=(bin[i>>1]>>1)|((i&1)*(n>>1));
        for(LL i=0;i<n;i++) if(i<bin[i]) swap(a[i],a[bin[i]]);
        for(LL i=1;i<n;i<<=1)
        {
            LL wn=pow(yg,op==1?(p-1)/(2*i):(p-1)-(p-1)/(2*i)),w,t;
            for(LL j=0;j<n;j+=i<<1)
            {
                w=1;
                for(LL k=0;k<i;k++)
                {
                    t=a[i+j+k]*w%p;w=w*wn%p;
                    a[i+j+k]=(a[j+k]-t+p)%p;a[j+k]=(a[j+k]+t)%p;
                }
            }
        }
        if(op==-1)
        {
            LL Inv=pow(n,p-2);
            for(LL i=0;i<n;i++) a[i]=a[i]*Inv%p;
        }
    }
    void dfs(LL x,LL fa)
    {
    	size[x]=1;A[n]++;
    	for(LL i=last[x];i;i=a[i].next)
    	{
    		LL y=a[i].y;
    		if(y==fa) continue;
    		dfs(y,x);size[x]+=size[y];
    		A[size[y]]--;
    	}
    	if(n-size[x]) A[n-size[x]]--;
    }
    //LL C(LL m,LL n) {return f[m]*inv[m-n]%p*inv[n]%p;}
    int main()
    {
    	scanf("%lld",&n);
    	for(LL i=1;i<n;i++)
    	{
    		LL x,y;scanf("%lld %lld",&x,&y);
    		ins(x,y);ins(y,x);
    	}
    	pre();dfs(1,0);
    	for(LL i=0;i<=n;i++) B[i]=inv[i],A[i]+=A[i]<0?p:0,A[i]=A[i]*f[i]%p;
    	reverse(B,B+n+1);
    	LL N=1;while(N<(n+1)<<1) N<<=1;
    	ntt(A,N,1);ntt(B,N,1);
    	for(LL i=0;i<N;i++) A[i]=A[i]*B[i]%p;
    	ntt(A,N,-1);
    	for(LL i=1;i<=n;i++) printf("%lld\n",inv[i]*A[n+i]%p);
    }