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>
#define ll long long
#define fo(i,x,y) for(int i=x;i<=y;i++)
#define fd(i,x,y) for(int i=x;i>=y;i--)
using namespace std;

const int maxn=600007,mo=924844033,G=5;

int n,fi[maxn],ne[maxn],la[maxn],tot;
void add(int a,int b){
	tot++;
	ne[tot]=fi[a];
	la[tot]=b;
	fi[a]=tot;
}

int f[maxn];
int b[maxn],si[maxn],fa[maxn];
void bfs(){
	b[b[0]=1]=1;
	fo(i,1,b[0]){
		int v=b[i];
		for(int k=fi[v];k;k=ne[k])
			if (la[k]!=fa[v]){
				b[++b[0]]=la[k];
				fa[la[k]]=v;
			}
		si[v]=1;
	}
	fd(i,b[0],2){
		int v=b[i];
		for(int k=fi[v];k;k=ne[k])
			if (la[k]!=fa[v])
				si[v]+=si[la[k]];
		f[si[v]]++;
		f[n-si[v]]++;
	}
}
int qp(int a,int b){
	int c=1;
	while (b){
		if (b&1) c=1ll*a*c%mo;
		a=1ll*a*a%mo;
		b>>=1;
	}
	return c;
}
int N=1,w[maxn],_w[maxn],Fact[maxn],invFact[maxn];
void pre(){
	while (N<n*2) N<<=1;
	int t=qp(G,(mo-1)/N);
	w[0]=1;
	fo(i,1,N) w[i]=1ll*w[i-1]*t%mo;
	fo(i,0,N) _w[i]=w[N-i];
	Fact[0]=1;
	fo(i,1,N) Fact[i]=Fact[i-1]*1ll*i%mo;
	invFact[N-1]=qp(Fact[N-1],mo-2);
	fd(i,N-2,0) invFact[i]=invFact[i+1]*(i+1ll)%mo;
}
void Init(){
	scanf("%d",&n);
	fo(i,1,n-1){
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	}
	bfs();
	pre();
}

int g[maxn];
void DFT(int *x,int *w){
	for(int i=0,j=0;i<N;i++){
		if (i<j) swap(x[i],x[j]);
		for(int l=N>>1;(j^=l)<l;l>>=1);
	}
	for(int i=2,m=1;i<=N;i<<=1,m<<=1)
		for(int j=0;j<N;j+=i)
			fo(k,0,m-1){
				int tmp=1ll*x[j+k+m]*w[N/i*k]%mo;
				x[j+k+m]=(x[j+k]-tmp+mo)%mo;
				x[j+k]=(x[j+k]+tmp)%mo;
			}
}
void NTT(int *a,int *b){
	DFT(a,w);
	DFT(b,w);
	fo(i,0,N-1) a[i]=1ll*a[i]*b[i]%mo;
	DFT(a,_w);
	int inv=qp(N,mo-2);
	fo(i,0,N-1) a[i]=1ll*a[i]*inv%mo;
}
void Solve(){
	fo(i,0,N-1) f[i]=1ll*f[i]*Fact[i]%mo;
	reverse(f,f+n+1);
	fo(i,0,n) g[i]=invFact[i];
	NTT(f,g);
}

int C(int x,int y){
	return 1ll*Fact[x]*invFact[y]%mo*invFact[x-y]%mo;
}
void Print(){
	fo(i,1,n) printf("%d\n",((1ll*n*C(n,i)-f[n-i]*1ll*invFact[i])%mo+mo)%mo);
}

int main(){
	Init();
	Solve();
	Print();
	return 0;
}