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<cstring>
#define retrun return
#define cpnst const
typedef long long ll;
cpnst ll mod=924844033,g=5;
ll qpow(ll x,ll k){ll r=1;for(;k;k>>=1,(x*=x)%=mod)if(k&1)(r*=x)%=mod;return r;}
int rev[1111111],V;
void resiz(int _v)
{
	V=_v;
	register int i;
	for(i=1;i<V;i++)rev[i]=(rev[i>>1]>>1)|((i&1)*(V>>1));
}
int wi[1111111];
void swap(register ll&x,register ll&y)
{x^=y^=x^=y;}
void NTT(ll*x,int op)
{
	register int i,ii,iii;
	for(i=1;i<V;i++)if(rev[i]>i)swap(x[i],x[rev[i]]);
	wi[0]=1;
	for(i=1;i<V;i<<=1)
	{
		register int w=qpow(g,(mod-1)/(i<<1));
		if(op<0)w=qpow(w,mod-2);
		for(register int*p=wi+1;p<wi+i;p++)*p=*(p-1)*1ll*w%mod;
		for(ii=0;ii<V;ii+=(i<<1))
			for(iii=0;iii<i;iii++)
			{
				int px=ii+iii,py=px+i;
				ll vx=x[px]+wi[iii]*x[py],vy=x[px]-wi[iii]*x[py];
				x[px]=vx%mod,x[py]=vy%mod; 
			}
	}ll t=op>0?1:qpow(V,mod-2);
	for(i=0;i<V;i++)x[i]=(x[i]+mod)*t%mod;
}
#include<vector>
int n;
std::vector<int>v[222222];
int cnt[1111111],siz[1111111];
void dfs(int p=1,int f=0)
{
	siz[p]=1;
	for(auto t:v[p])if(t^f)dfs(t,p),siz[p]+=siz[t],cnt[siz[t]]++;
	if(siz[p]^n)cnt[n-siz[p]]++;
}
ll Tp[1111111],Tg[1111111];
void mul(ll*x,ll*y,int CyC)
{
	resiz(CyC);
	register int i;
	for(i=0;i<(CyC>>1);i++)Tp[i]=x[i],Tg[i]=y[i];
	for(i=CyC>>1;i<CyC;i++)Tp[i]=Tg[i]=0;
	NTT(Tp,1),NTT(Tg,1);
	for(i=0;i<CyC;i++)(Tp[i]*=Tg[i])%=mod;
	NTT(Tp,-1);
	for(i=0;i<(CyC>>1);i++)x[i]=Tp[i];
}
ll fac[1111111],inv[1111111],A[1111111],B[1111111];
ll C(ll n,ll r){return fac[n]*inv[r]%mod*inv[n-r]%mod;}
void solve()
{
	register int i;
	for(i=fac[0]=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;
	for(i=n,inv[i]=qpow(fac[i],mod-2);i;i--)inv[i-1]=inv[i]*i%mod;
	for(i=0;i<=n;i++)A[i]=fac[n-i]*cnt[n-i]%mod,B[i]=inv[i]%mod;
	mul(A,B,524288);
	for(i=1;i<=n;i++)printf("%lld\n",(n*C(n,i)+mod-A[n-i]*inv[i]%mod)%mod);
}
int main()
{
	scanf("%d",&n);
	register int i;
	for(i=1;i<n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
	}dfs(),solve();
}