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>
using namespace std;
#define LL long long
#define C(n,m) ((LL)fac[n]*ifac[m]%mo*ifac[(n)-(m)]%mo)

const int maxn=2<<19;
const int mo=924844033;

int n,sz[maxn],fac[maxn],ifac[maxn];
int tote,FIR[maxn],TO[maxn],NEXT[maxn];
int step,N,rev[maxn],wn[maxn];
int cc[maxn],bb[maxn],aa[maxn];

void addedge(int u,int v)
{
	TO[++tote]=v;
	NEXT[tote]=FIR[u];
	FIR[u]=tote;
}

void search(int u,int F)
{
	sz[u]=1;
	for (int p=FIR[u];p;p=NEXT[p])
	{
		int v=TO[p];
		if (v!=F)
		{
			search(v,u);
			sz[u]+=sz[v];
			cc[sz[v]]++;
			cc[n-sz[v]]++;
		}
	}
}

int power(int x,int k)
{
	int res=1;
	while (k)
	{
		if (k&1) res=(LL)res*x%mo;
		x=(LL)x*x%mo;
		k>>=1;
	}
	return res;
}

void fft(int a[],int flag)
{
	int i,j,k;
	for (i=0;i<N;i++)
		if (i<rev[i]) swap(a[i],a[rev[i]]);
	for (k=1;k<N;k<<=1)
	{
		int p=N+flag*N/(k<<1);
		for (i=0;i<N;i+=k<<1)
		{
			for (j=0;j<k;j++)
			{
				int x=a[i+j];
				int y=(LL)a[i+j+k]*wn[(LL)j*p%N]%mo;
				a[i+j]=(x+y)%mo;
				a[i+j+k]=(x+mo-y)%mo;
			}
		}
	}
	if (flag==-1)
	{
		int inv=power(N,mo-2);
		for (i=0;i<N;i++)
			a[i]=(LL)a[i]*inv%mo;
	}
}

int main()
{
#ifdef h10
	freopen("F.in","r",stdin);
	freopen("F.out","w",stdout);
#endif
	int i,u,v;
	scanf("%d",&n);
	fac[0]=1;
	for (i=1;i<=n;i++)
		fac[i]=(LL)fac[i-1]*i%mo;
	ifac[n]=power(fac[n],mo-2);
	for (i=n;i>=1;i--)
		ifac[i-1]=(LL)ifac[i]*i%mo;
	for (i=1;i<n;i++)
	{
		scanf("%d%d",&u,&v);
		addedge(u,v);
		addedge(v,u);
	}
	search(1,0);
	for (i=1;i<=n;i++)
		cc[i]=(LL)cc[i]*fac[i]%mo;
	for (i=0;i<=n;i++)
		bb[i]=ifac[n-i];

	for (step=0,N=1;N<=n+n;step++,N<<=1);
	int w=power(5,(mo-1)/N);
	wn[0]=1;
	for (i=1;i<N;i++)
		wn[i]=(LL)wn[i-1]*w%mo;
	for (i=0;i<N;i++)
		rev[i]=(rev[i>>1]>>1)|((i&1)<<(step-1));
	fft(cc,+1);
	fft(bb,+1);
	for (i=0;i<N;i++)
		aa[i]=(LL)cc[i]*bb[i]%mo;
	fft(aa,-1);
	for (i=1;i<=n;i++)
	{
		int A=(n-1ll)*C(n,i)%mo;
		int B=(LL)aa[n+i]*ifac[i]%mo;
		printf("%lld\n",((A+mo-B)%mo+C(n,i))%mo);
	}
}