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 pb push_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) ((int)x.size())
#define FOR(i,a,b) for (int i=a;i<=b;++i)
#define FORD(i,a,b) for (int i=a;i>=b;--i)
using namespace std;
typedef long long LL;
typedef pair<int,int> pa;
typedef vector<LL> vec;
void getint(int &v){
    char ch,fu=0;
    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());
    if(ch=='-') fu=1, ch=getchar();
    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';
    if(fu) v=-v;
}
const int MO=924844033;
const int g=5;
LL fac[1000010],inv[1000010],ans[1000010];
int n,m,LOG2[1000010],siz[500010],R[1000010],tmp[500010],x,y,hed[500010],too[500010],nxt[500010],nedge;
vec A,B;
LL pw(LL x,LL y){
	LL t=1;
	for (;y;y>>=1){
		if (y&1) t=t*x%MO;
		x=x*x%MO;
	}
	return t;
}
LL C(int x,int y){
	return fac[x]*inv[y]%MO*inv[x-y]%MO;
}
void ae(int x,int y){
	nxt[++nedge]=hed[x];
	hed[x]=nedge;
	too[nedge]=y;
}
void dfs(int x,int l){
	siz[x]=1;
	for (int i=hed[x];i;i=nxt[i]){
		int y=too[i];
		if (y==l) continue;
		dfs(y,x);
		siz[x]+=siz[y];
	}
	if (x>1) ++tmp[siz[x]],++tmp[n-siz[x]];
}
void fft(vec &a,int tp){
	int n=SZ(a);
	int L=LOG2[n];
	FOR(i,1,n-1) R[i]=(R[i>>1]>>1)|((i&1)<<(L-1));
	FOR(i,1,n-1) if (i<R[i]) swap(a[i],a[R[i]]);
	for (int i=1;i<n;i<<=1){
		LL wn=pw(g,(tp==1)?((MO-1)/i/2):(MO-1-((MO-1)/i/2)));
		for (int p=i<<1,j=0;j<n;j+=p){
			LL w=1;
			for (int k=0;k<i;++k,w=w*wn%MO){
				LL x=a[j+k],y=a[j+k+i];
				a[j+k]=(x+y*w)%MO,a[j+k+i]=(x-y*w)%MO;
			}
		}
	}
	if (tp==-1){
		LL t=pw(n,MO-2);
		FOR(i,0,n-1) a[i]=a[i]*t%MO;
	}
}
int main(){
	cin>>n;
	fac[0]=1;
	FOR(i,1,1000000) fac[i]=fac[i-1]*i%MO;
	inv[1000000]=pw(fac[1000000],MO-2);
	FORD(i,999999,0) inv[i]=inv[i+1]*(i+1)%MO;
	FOR(i,1,1000000) LOG2[i]=log2(i);
	FOR(i,2,n){
		getint(x),getint(y);
		ae(x,y),ae(y,x);
	}
	dfs(1,0);
	m=1;
	while (m<=n+n) m<<=1;
	A.resize(m);
	B.resize(m);
	FOR(i,0,n) (A[n-i]+=fac[i]*tmp[i])%=MO;
	FOR(i,0,n) B[i]=inv[i];
	fft(A,1);
	fft(B,1);
	FOR(i,0,m-1) A[i]=A[i]*B[i]%MO;
	fft(A,-1);
	FOR(i,1,n) ans[i]=((C(n,i)*n-A[n-i]*inv[i])%MO+MO)%MO;
	FOR(i,1,n) printf("%lld\n",ans[i]);
	return 0;
}