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 <cmath>
#include <ctime>
#include <cstdio>
#include <algorithm>
#define Pi acos(-1.0)

using namespace std;

const int N=8e5+10,Mod=924844033;

struct Edge{ int to,next;} way[N<<1];

int n,num[N],tot,A[N],B[N],P[N],F[N<<4],fact[N],fact_inv[N];

void Build(int a,int b) { way[++tot]=(Edge){b,num[a]}; num[a]=tot; }

void Init()
{
	scanf("%d",&n);
	int a,b;
	for (int i=2;i<=n;++i)
	{
		scanf("%d%d",&a,&b);
		Build(a,b); Build(b,a);
	}
}

int son[N];
void Dfs(int x,int fa)
{
	son[x]=1;
	for (int i=num[x];i;i=way[i].next)
	{
		int v=way[i].to;
		if (v==fa) continue;
		Dfs(v,x);
		son[x]+=son[v];
		A[son[v]]--;
	}
	if (n-son[x]) A[n-son[x]]--;
}

int R[N<<2],L;
int inv(int x)
{
	int t=Mod-2,ret=1;
	while (t)
	{
		if (t&1) ret=1ll*ret*x%Mod;
		x=1ll*x*x%Mod;
		t>>=1;
	}
	return ret;
}

int qpow(int x,int k)
{
	int ret=1;
	while (k)
	{
		if (k&1) ret=1ll*ret*x%Mod;
		x=1ll*x*x%Mod;
		k>>=1;
	}
	return ret;
}

void BRC(int *y,int len)
{
	for (int i=0;i<len;++i) 
		if (R[i]<i) swap(y[i],y[R[i]]);
}

void ntt(int *y,int len,int f)
{
	BRC(y,len);
	fprintf(stderr,"%d\n",clock());
	for (int h=2;h<=len;h<<=1)
	{
		int wn=qpow(5,(Mod-1)/h);
		if (f==-1) wn=qpow(wn,Mod-2);
		for (int j=0;j<len;j+=h)
		{
			int w=1;
			for (int k=j;k<j+h/2;++k)
			{
				int u=y[k],t=1ll*w*y[k+h/2]%Mod;
				y[k]=(u+t)%Mod;
				y[k+h/2]=(u-t+Mod)%Mod;
				w=1ll*w*wn%Mod;
			}
		}
	}
    if(f==-1){
        int ny=qpow(len,Mod-2);
        for(int i=0;i<len;i++) 
			y[i]=1ll*y[i]*ny%Mod;
    }
}

void Solve()
{
	Dfs(1,0);A[n]=n; 
	fact[0]=1; for (int i=1;i<=n;++i) fact[i]=1ll*fact[i-1]*i%Mod;
	int ny=inv(fact[n]);fact_inv[n]=ny;
	for (int i=n-1;i;--i) fact_inv[i]=1ll*fact_inv[i+1]*(i+1)%Mod;
	fact_inv[0]=1;
	for (int i=0;i<=n;++i) B[i]=fact_inv[i];
	for (int i=0;i<=n;++i) A[i]=1ll*(A[i]+Mod)*fact[i]%Mod;
	for (int i=0;i<=n;++i) P[i]=A[n-i];
	
	int len,L=0; for (len=1;len<((n+1)<<1);len<<=1) ++L;
    for(int i=0;i<len;i++)R[i]=R[i>>1]>>1|((i&1)<<(L-1));
	ntt(P,len,1); ntt(B,len,1); 
    for(int i=0;i<len;i++)F[i]=1ll*P[i]*B[i]%Mod;
//    for (int i=0;i<len;++i) printf("%d%c",F[i],i==len-1?'\n':' ');
    ntt(F,len,-1);
	for (int i=n-1;i>=0;--i) 
		printf("%lld\n",1ll*F[i]*fact_inv[n-i]%Mod);
}

int main()
{
	Init();
	Solve();
	return 0;
}