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>
typedef long long ll;
const int N=2e5+3,K=19,M=924844033,G=5;
inline int Pow(int a,int m){int s=1;for(;m;m>>=1)m&1?s=(ll)s*a%M:0,a=(ll)a*a%M;return s;}
struct edge{int v,nxt;}g[N+N];
int n,f[N],invf[N],b[N],siz[N],head[N],k,t0[1<<K],t1[1<<K],rev[1<<K];
inline void Insert(int u,int v){g[++k]=(edge){v,head[u]};head[u]=k;}
void Dfs(int u,int fa){
	int v;
	siz[u]=1;
	for(int i=head[u];i;i=g[i].nxt)if((v=g[i].v)!=fa)
	  Dfs(v,u),siz[u]+=siz[v];
	if(fa)b[siz[u]]++,b[n-siz[u]]++; 
}
inline void Init(int K){
	for(int i=0;i<(1<<K);i++)rev[i]=rev[i>>1]>>1|(i&1)*(1<<K-1);
}
inline void Ntt(int*a,int f,int K){
	int tmp,tmp1,omega;
	for(int i=0;i<(1<<K);i++)if(i<rev[i])tmp=a[i],a[i]=a[rev[i]],a[rev[i]]=tmp;
	for(int k=1;k<(1<<K);k<<=1){
	  omega=Pow(G,f>0?M/2/k:M-1-M/2/k);
	  for(int i=0;i<(1<<K);i+=k+k)
		for(int j=0,s=1;j<k;j++,s=(ll)s*omega%M)
		  tmp=a[i+j],tmp1=(ll)a[i+k+j]*s%M,
		  a[i+j]=(tmp+tmp1)%M,a[i+k+j]=(tmp-tmp1+M)%M;
	  }
	if(f<0){
	  tmp=Pow(1<<K,M-2);
	  for(int i=0;i<(1<<K);i++)
		a[i]=(ll)a[i]*tmp%M;
	}
}
int main(){
	int u,v;
	scanf("%d",&n);
	f[0]=1;
	for(int i=1;i<=n;i++)f[i]=(ll)f[i-1]*i%M;
	invf[n]=Pow(f[n],M-2);
	for(int i=n;i;i--)invf[i-1]=(ll)invf[i]*i%M;
	for(int i=1;i<n;i++)scanf("%d%d",&u,&v),Insert(u,v),Insert(v,u);
	Dfs(1,0);
	for(int i=1;i<=n;i++)t0[i]=(ll)b[i]*f[i]%M;
	for(int i=0;i<=n;i++)t1[i]=invf[n-i];
	for(k=1;(1<<k)<=n+n;k++);
	Init(k);
	Ntt(t0,1,k),Ntt(t1,1,k);
	for(int i=0;i<(1<<K);i++)t0[i]=(ll)t0[i]*t1[i]%M;
	Ntt(t0,-1,k);
	for(int k=1;k<=n;k++)printf("%lld\n",((ll)n*f[n]%M*invf[k]%M*invf[n-k]%M-(ll)invf[k]*t0[n+k]%M+M)%M);
	return 0;
}