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 cs const
#define pb push_back
#define rez resize
#define bg begin
#define poly vector<int>
using namespace std;
cs int Mod = 924844033;
int add(int a, int b){ return a + b >= Mod ? a + b - Mod : a + b; }
int dec(int a, int b){ return a - b < 0 ? a - b + Mod : a - b; }
int mul(int a, int b){ return 1ll * a * b % Mod; }
void Add(int &a, int b){ a = add(a,b); }
void Mul(int &a, int b){ a = mul(a,b); }
void Dec(int &a, int b){ a = dec(a,b); }
int ksm(int a, int b){ int as=1; for(;b;b>>=1,Mul(a,a)) if(b&1) Mul(as,a); return as; }
cs int N = 2e5 + 50;
int n, sz[N]; vector<int> G[N];
int fc[N], ifc[N]; poly f, g;
int C(int n, int m){ return mul(fc[n],mul(ifc[n-m],ifc[m])); }
void fc_init(int n){
	fc[0]=fc[1]=ifc[0]=ifc[1]=1;
	for(int i=2;i<=n;i++)fc[i]=mul(fc[i-1],i);
	ifc[n]=ksm(fc[n],Mod-2);
	for(int i=n-1;i>=2;i--)ifc[i]=mul(ifc[i+1],i+1);
}
void dfs(int u, int fa){
	sz[u]=1; for(int v:G[u])
	if(v!=fa) dfs(v,u),sz[u]+=sz[v],++f[sz[v]];
	++f[n-sz[u]];
}
cs int M = 1 << 19;
int up, bit, rv[M];
void init(int d){
	up=1, bit=0; while(up<d) up<<=1,++bit;
	for(int i=0; i<up; i++) 
	rv[i] = (rv[i>>1]>>1)|((i&1)<<(bit-1));
}
void dft(poly &a){
	for(int i=0;i<up;i++) 
	if(i<rv[i]) swap(a[i],a[rv[i]]);
	for(int i=1;i<up;i<<=1)
	for(int j=0,t=i<<1,wn=ksm(5,(Mod-1)/t);j<up;j+=t)
	for(int k=0,w=1;k<i;k++,Mul(w,wn)){
		int x=a[k+j], y=mul(w,a[k+j+i]);
		a[k+j]=add(x,y), a[k+j+i]=dec(x,y);
	} 
} void idft(poly &f){ 
	dft(f); reverse(f.bg()+1,f.end());
	for(int i=0,iv=ksm(up,Mod-2);i<up;i++)
	Mul(f[i],iv);
}
int main(){
	#ifdef FSYolanda
	freopen("1.in","r",stdin);
	#endif
	scanf("%d",&n); fc_init(n);
	for(int i=1,u,v;i<n;i++)
	scanf("%d%d",&u,&v),G[u].pb(v),G[v].pb(u);
	f.rez(n+1); g.rez(n+1); dfs(1,0);
//	for(int i=1;i<=n;i++)cout<<f[i]<<" ";cout<<endl;
	for(int i=1;i<=n;i++) Mul(f[i],fc[i]); 
	reverse(f.bg(),f.end());
	for(int i=0; i<=n; i++) g[i]=ifc[i];
	init(n+n+1); f.rez(up), g.rez(up);
	dft(f), dft(g);
	for(int i=0;i<up;i++)Mul(f[i],g[i]);
	idft(f); 
//	for(int i=1; i<=n; i++) cout << mul(ifc[i],f[n-i]) << endl;
	for(int i=1;i<=n;i++)
	cout<<dec(mul(n,C(n,i)),mul(ifc[i],f[n-i]))<<'\n';
	return 0;
}