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>
#define L long long
#define LL long long
using namespace std;
const int q=924844033;
const int M = 21, P = 924844033, G = 5;
const int MaxN = (1 << 20) + 10;
int N = 1 << 19;

inline int add(int a, int b) {
    return (a + b) % P;
}

inline int sub(int a, int b) {
    return (a - b + P) % P;
}

inline int mul(int a, int b) {
    return (LL)a * (LL)b % P;
}

inline int exp(int a, int b) {
    int ans = 1;
    for (; b; b >>= 1) {
        if (b & 1) ans = mul(ans, a);
        a = mul(a, a);
    }
    return ans;
}

inline int inv(int x) {
    return exp(x, P - 2);
}

int eps[MaxN], ieps[MaxN], temp[5][MaxN];

inline void init() {
    int g = exp(G, (P - 1) / N), ig = inv(g);
    eps[0] = ieps[0] = 1;
    for (int i = 1; i < N; i++) eps[i] = mul(eps[i - 1], ig), ieps[i] = mul(ieps[i - 1], g);
}

inline void trans(int n, int x[], int w[]) {
    for (int i = 0, j = 0; i != n; i++) {
        if (i < j) std::swap(x[i], x[j]);
        for (int l = n >> 1; (j ^= l) < l; l >>= 1);
    }
    for (int i = 2; i <= n; i <<= 1) {
        int l = i >> 1, d = N / i;
        for (int j = 0; j != n; j += i)
            for (int k = 0; k != l; k++) {
                int t = mul(x[j + k + l], w[d * k]);
                x[j + k + l] = sub(x[j + k], t);
                x[j + k] = add(x[j + k], t);
            }
    }
}

inline void dft(int n, int x[]) {
    trans(n, x, eps);
}

inline void idft(int n, int x[]) {
    trans(n, x, ieps);
    for (int i = 0, in = inv(n); i < n; i++) x[i] = mul(x[i], in);
}

int n,x[800010],y[800010],p;
vector<int> a[200010];
inline int dfs(int i,int j)
{
	int k,l=1,u;
	for(k=0;k<a[i].size();k++)
	  if(a[i][k]!=j)
	    {
		 u=dfs(a[i][k],i);
		 l+=u;
		 x[u]++;
		 x[n-u]++;
		}
	return l;
}
int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	int i,j,k;
	init();
	scanf("%d",&n);
	for(i=1;i<n;i++)
	  {
	   scanf("%d%d",&j,&k);
	   a[j].push_back(k);
	   a[k].push_back(j);
	  }
	dfs(1,0);
	y[n]=1;
	for(i=1,k=1;i<=n;i++,k=(L)k*i%q)
	  {
	   x[i]=(L)x[i]*k%q;
	   y[n-i]=exp(k,q-2);
	  }
	for(p=1;p<n;p<<=1);
	p<<=1;
	dft(p,x);
	dft(p,y);
	for(i=0;i<p;i++)
	  x[i]=(L)x[i]*y[i]%q;
	idft(p,x);
	for(i=1,j=n,k=1;i<=n;i++,j=(L)j*(n-i+1)%q*exp(i,q-2)%q,k=(L)k*i%q)
	  printf("%d\n",int(((L)j*n-(L)x[n+i]*exp(k,q-2))%q+q)%q);
	return 0;
}