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<cstring>
#include<iostream>
#define For(i,x,y) for(int i=x;i<=y;++i)
using namespace std;
const int N = 800005;
const int P = 924844033;
int pow(int x,int y){
	int p=1;
	for(;y;y>>=1,x=(1ll*x*x)%P)
		if(y&1)p=(1ll*p*x)%P;return p;
}
int inv(int x){return pow(x,P-2);}
int n,k,L;
int w0[N],w1[N];
int head[N],nxt[N],to[N],cnt;
int fac[N],Inv[N],tmp[N];
int A[N],B[N]; 
void add(int u,int v){
	nxt[++cnt]=head[u];head[u]=cnt;to[cnt]=v;
	nxt[++cnt]=head[v];head[v]=cnt;to[cnt]=u;
}
void init_w(){
	w0[0]=w1[0]=1;
	w0[1]=pow(5,(P-1)/L);w1[1]=inv(w0[1]);
	For(i,2,L){
		w0[i]=1ll*w0[i-1]*w0[1]%P;
		w1[i]=1ll*w1[i-1]*w1[1]%P;
	}
}
void ntt(int n,int*buf,int beg,int step,int*w){
	if(n==1) return;
	int m=n>>1;
	ntt(m,buf,beg,step<<1,w);
	ntt(m,buf,beg+step,step<<1,w);
	For(i,0,m-1){
		int pos=2*i*step;
		tmp[i]=(1ll*buf[beg+pos]+(1ll*w[i*step]*buf[beg+pos+step])%P)%P;
		tmp[i+m]=(1ll*buf[beg+pos]-(1ll*w[i*step]*buf[beg+pos+step])%P+P)%P;
	}
	For(i,0,n-1) buf[beg+i*step] = tmp[i]%P;
}
int sz[N];
long long ans[N];
long long C(int n,int m){return (1ll*fac[n]*Inv[m]%P)*Inv[n-m]%P;}
void dfs(int u,int fat){
	sz[u]=1;
	for(int i=head[u];i;i=nxt[i]){
		int v=to[i];if(v==fat) continue;
		dfs(v,u);sz[u]+=sz[v];A[sz[v]]++;
	}
	A[n-sz[u]]++;
}
int main(){
//	freopen("ha.in","r",stdin);
//	freopen("ha.out","w",stdout);
	scanf("%d",&n);
	fac[0]=1;For(i,1,n)fac[i]=(1ll*fac[i-1]*i)%P;
	For(i,0,n)Inv[i]=inv(fac[i]);
	for(L=1;L<=n;L<<=1);L<<=1;
	For(i,1,n-1){
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v);
	}
	dfs(1,1);
	For(i,1,n) A[i] = (1ll*A[i]*fac[i])%P;
	For(i,0,n) B[n-i] = Inv[i];
	init_w();
	ntt(L,A,0,1,w0);
	ntt(L,B,0,1,w0);
	For(i,0,L-1) A[i] = (1ll*A[i]*B[i])%P;
	ntt(L,A,0,1,w1);
	int Inv_L = inv(L);
	For(i,0,L-1) A[i] = (1ll*A[i]*Inv_L)%P;
	For(k,1,n){
		ans[k]=(1ll*(P-1)*Inv[k]%P*A[k+n])%P;
		ans[k]=(ans[k]+1ll*C(n,k)*k+1ll*C(n-1,k)*n)%P;
	}
	For(i,1,n){
		while(ans[i]<0)ans[i]+=P;
		printf("%d\n",ans[i]);
	}
	return 0;
}