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<algorithm>
using namespace std;
int gi(){
	int x=0,w=1;char ch=getchar();
	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if (ch=='-') w=0,ch=getchar();
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
const int N = 6e5+5;
const int mod = 924844033;
int n,to[N],nxt[N],head[N],cnt,sz[N],ans[N],tmp[N],rev[N],og[N],inv[N],jc[N],jcn[N];
void dfs(int u,int f){
	sz[u]=1;
	for (int e=head[u];e;e=nxt[e])
		if (to[e]!=f){
			dfs(to[e],u),sz[u]+=sz[to[e]];
			++ans[sz[to[e]]],++ans[n-sz[to[e]]];
		}
}
int fastpow(int a,int b){
	int res=1;
	while (b) {if (b&1) res=1ll*res*a%mod;a=1ll*a*a%mod;b>>=1;}
	return res;
}
void init(int len){
	int l=0;while (1<<l<len) ++l;
	for (int i=0;i<len;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<l-1);
}
void ntt(int *P,int op,int len){
	for (int i=0;i<len;++i) if (i<rev[i]) swap(P[i],P[rev[i]]);
	for (int i=1;i<len;i<<=1){
		int W=fastpow(5,(mod-1)/(i<<1));
		if (op==-1) W=fastpow(W,mod-2);
		og[0]=1;for (int j=1;j<i;++j) og[j]=1ll*og[j-1]*W%mod;
		for (int p=i<<1,j=0;j<len;j+=p)
			for (int k=0;k<i;++k){
				int x=P[j+k],y=1ll*P[j+k+i]*og[k]%mod;
				P[j+k]=(x+y)%mod,P[j+k+i]=(x-y+mod)%mod;
			}
	}
	if (op==-1) for (int i=0,Inv=fastpow(len,mod-2);i<len;++i) P[i]=1ll*P[i]*Inv%mod;
}
int main(){
	n=gi();inv[1]=jc[0]=jcn[0]=1;
	for (int i=2;i<=n;++i) inv[i]=1ll*inv[mod%i]*(mod-mod/i)%mod;
	for (int i=1;i<=n;++i) jc[i]=1ll*jc[i-1]*i%mod,jcn[i]=1ll*jcn[i-1]*inv[i]%mod;
	for (int i=1;i<n;++i){
		int u=gi(),v=gi();
		to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;
		to[++cnt]=u;nxt[cnt]=head[v];head[v]=cnt;
	}
	dfs(1,0);int len=1;while (len<=n<<1) len<<=1;
	for (int i=1;i<=n;++i) ans[i]=1ll*ans[i]*jc[i]%mod,tmp[i]=jcn[n-i];
	init(len);ntt(ans,1,len);ntt(tmp,1,len);
	for (int i=0;i<len;++i) ans[i]=1ll*ans[i]*tmp[i]%mod;
	ntt(ans,-1,len);
	for (int i=1;i<=n;++i) printf("%lld\n",(1ll*n*jc[n]%mod*jcn[n-i]-ans[n+i]+mod)%mod*jcn[i]%mod);
	return 0;
}