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<bits/stdc++.h>
using namespace std;
long long read()
{
	char ch=getchar();long long x=0,ff=1;
	while(ch<'0'||ch>'9') {if(ch=='-') ff=-ff;ch=getchar();}
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x*ff;
}
void write(long long aa)
{
	if(aa<0) putchar('-'),aa=-aa;
	if(aa>9) write(aa/10);
	putchar(aa%10+'0');
	return;
}
const long long mod=924844033;
long long n,m;
long long tot,head[200005],nx[400005],to[400005];
long long fac[200005],ny[200005];
long long jl[200005],sz[200005];
long long bh[1400005],A[1400005],B[1400005];
void jia(long long aa,long long bb)
{
	tot++;
	nx[tot]=head[aa];
	to[tot]=bb;
	head[aa]=tot;
	return;
}
long long ksm(long long aa,long long bb)
{
	long long now=1;
	while(bb)
	{
		if(bb&1) now=now*aa%mod;
		bb>>=1;aa=aa*aa%mod;
	}
	return now;
}
void dfs(long long rt,long long fa)
{
	sz[rt]=1;
	for(long long i=head[rt];i;i=nx[i])
	{
		long long yy=to[i];
		if(yy==fa) continue;
		dfs(yy,rt);sz[rt]+=sz[yy];
	}
	if(fa) jl[sz[rt]]++,jl[n-sz[rt]]++;
	return;
}
void ntt(long long* a,long long ff)
{
	for(long long i=0;i<m;++i) if(bh[i]>i) swap(a[i],a[bh[i]]);
	for(long long i=1;i<m;i<<=1)
	{
		long long yuan=ksm(5,(mod-1)/(i*2));
		if(ff==-1) yuan=ksm(yuan,mod-2);
		for(long long j=0;j<m;j+=(i<<1))
		for(long long l=0,now=1;l<i;++l,now=now*yuan%mod)
		{
			long long aa=a[j+l],bb=now*a[j+i+l]%mod;
			a[j+l]=(aa+bb)%mod;a[j+i+l]=(aa-bb+mod)%mod;
		}
	}
	return;
}
long long C(long long aa,long long bb) 
{
	if(bb<aa) return 0;
	return fac[bb]*ny[aa]%mod*ny[bb-aa]%mod;
}
int main()
{
	n=read();
	for(long long i=1;i<n;++i)
	{
		long long x=read(),y=read();
		jia(x,y);jia(y,x);
	}
	dfs(1,0);fac[0]=1;
	for(long long i=1;i<=n;++i) fac[i]=fac[i-1]*i%mod;
	ny[n]=ksm(fac[n],mod-2);
	for(long long i=n;i;i--) ny[i-1]=ny[i]*i%mod;
	m=1;while(m<=n*2) m<<=1;
	for(long long i=1;i<m;++i) bh[i]=(bh[i>>1]>>1)|(i&1?(m>>1):0);
	for(long long i=0;i<=n;++i) A[i]=jl[i]*fac[i]%mod;
	for(long long i=0;i<=n;++i) B[i]=ny[n-i];
	ntt(A,1);ntt(B,1);
	for(long long i=0;i<m;++i) A[i]=A[i]*B[i]%mod;
	ntt(A,-1);long long NY=ksm(m,mod-2);
	for(long long i=1;i<=n;++i) write((n*C(i,n)%mod-A[i+n]*NY%mod*ny[i]%mod+mod)%mod),puts("");
	return 0;
}