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>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const LL MOD=924844033;
const LL g=5;
const LL gi=554906420;
const LL N=200005*8;
struct qq
{
	LL x,y,last;
}e[N*2];LL num,last[N];
LL n;
LL pow (LL x,LL y)
{
	if (y==1) return  x;
	LL lalal=pow(x,y>>1);
	lalal=lalal*lalal%MOD;
	if (y&1) lalal=lalal*x%MOD;
	return lalal;
}
void init (LL x,LL y)
{
	num++;
	e[num].x=x;e[num].y=y;
	e[num].last=last[x];
	last[x]=num;
}
LL tot[N];
LL a[N],b[N];
void dfs (LL x,LL fa)
{
	tot[x]=1;
	for (LL u=last[x];u!=-1;u=e[u].last)
	{
		LL y=e[u].y;
		if (y==fa) continue;
		dfs(y,x);
		tot[x]+=tot[y];
	}
	if (fa!=0) 	{a[tot[x]]++;a[n-tot[x]]++;}
}
LL JC[N],inv[N];
LL bin[N];
void ntt (LL *a,LL n,LL o)
{
	for (LL u=0;u<n;u++)	bin[u]=(bin[u>>1]>>1)|((u&1)*(n>>1));
	for (LL u=0;u<n;u++)
		if (u<bin[u])
			swap(a[u],a[bin[u]]);
	for (LL u=1;u<n;u<<=1)
	{
		LL w,t,wn=pow(o==1?g:gi,(MOD-1)/(u<<1));
		for (LL i=0;i<n;i=i+(u<<1))
		{
			w=1;
			for (LL j=0;j<u;j++)
			{
				t=w*a[u+i+j]%MOD;
				a[u+i+j]=(a[i+j]-t+MOD)%MOD;
				a[i+j]=(a[i+j]+t)%MOD;
				w=w*wn%MOD;
			}
		}
	}
	if (o==-1)
	{
		LL Inv=pow(n,MOD-2);for (LL u=0;u<n;u++) a[u]=a[u]*Inv%MOD;
	}
}
int main()
{
	//printf("%lld\n",pow(g,MOD-2));
	num=0;memset(last,-1,sizeof(last));
	scanf("%lld",&n);
	for (LL u=1;u<n;u++)
	{
		LL x,y;
		scanf("%lld%lld",&x,&y);
		init(x,y);init(y,x);
	}
	dfs(1,0);
	JC[0]=1;for (LL u=1;u<=n;u++) JC[u]=JC[u-1]*u%MOD;
	inv[n]=pow(JC[n],MOD-2);for (LL u=n-1;u>=0;u--) inv[u]=inv[u+1]*(u+1)%MOD;
	for (LL u=1;u<=n;u++) a[u]=a[u]*JC[u]%MOD;
	for (LL u=0;u<=n;u++) b[u]=inv[n-u];
	LL now=1;while (now<=n) now<<=1;now<<=1;
	ntt(a,now,1);ntt(b,now,1);
	for (LL u=0;u<now;u++) a[u]=a[u]*b[u]%MOD;
	ntt(a,now,-1);
	for (LL u=1;u<=n;u++)
	{
		now=JC[n]*inv[u]%MOD*inv[n-u]%MOD*n%MOD;
		now=(now-a[n+u]*inv[u]%MOD+MOD)%MOD;
		printf("%lld\n",now);
	}
	return 0;
}