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;
typedef long long lint;
typedef pair<int, int> pi;
const int mod = (441 << 21) + 1;

lint ipow(lint x, lint p){
	lint ret = 1, piv = x % mod;
	while(p){
		if(p&1) ret *= piv;
		piv *= piv;
		ret %= mod;
		piv %= mod;
		p >>= 1;
	}
	return ret % mod;
}

namespace nt_fft{
	const int prr = 5;
	void fft(vector<int> &v, bool inv){
		vector<int> w(v.size());
		for(int i=2; i<=v.size(); i<<=1){
			int bsz = v.size() / i;
			int ang = ipow(prr, (mod - 1) / i);
			if(inv) ang = ipow(ang, mod-2);
			for(int j=0; j<bsz; j++){
				for(int k=0; k<i; k++){
					w[k] = v[j + k * bsz];
				}
				lint cur = 1;
				for(int k=0; k<i/2; k++){
					lint a = w[2*k], b = cur * w[2*k+1] % mod;
					v[j + k * bsz] = (a + b) % mod;
					v[j + k * bsz + v.size()/2] = (a - b + mod) % mod;
					cur = (cur * ang) % mod;
				}
			}
		}
		if(inv){
			lint mul = ipow(v.size(), mod-2);
			for(int i=0; i<v.size(); i++){
				v[i] = (mul * v[i]) % mod;
			}
		}
	}
	vector<int> multiply(vector<int> a, vector<int> b){
		int w = 1;
		while(w < max(a.size(), b.size())) w <<= 1;
		w <<= 1;
		a.resize(w);
		b.resize(w);
		fft(a, 0); 
		fft(b, 0);
		for(int i=0; i<w; i++) a[i] = (1ll * a[i] * b[i]) % mod;
		fft(a, 1);
		return a;
	}
	vector<int> power(vector<int> a){
		int w = 1;
		while(w < a.size()) w <<= 1;
		w <<= 1;
		a.resize(w);
		fft(a, 0);
		for(int i=0; i<w; i++) a[i] = (1ll * a[i] * a[i]) % mod;
		fft(a, 1);
		return a;
	}
}

int n, k, sz[200005];
vector<int> gph[200005];
int cnt[200005];

void dfs(int x, int p){
	sz[x] = 1;
	cnt[n]++;
	for(auto &i : gph[x]){
		if(i == p) continue;
		dfs(i, x);
		cnt[sz[i]]--;
		sz[x] += sz[i];
	}
	cnt[n - sz[x]]--;
}

lint fact[200005], invf[200005];

int main(){
	cin >> n;
	for(int i=1; i<n; i++){
		int s, e;
		scanf("%d %d",&s,&e);
		gph[s].push_back(e);
		gph[e].push_back(s);
	}
	fact[0] = invf[0] = 1;
	for(int i=1; i<=n; i++){
		fact[i] = fact[i-1] * i % mod;
		invf[i] = ipow(fact[i], mod-2);
	}
	dfs(1, 0);
	for(int i=1; i<=n; i++){
		cnt[i] = fact[i] * (cnt[i] + mod) % mod;
	}
	vector<int> p1(n+1), p2(n+1);
	for(int i=0; i<=n; i++){
		p1[i] = invf[n-i];
		p2[i] = cnt[i]; 
	}
	auto w = nt_fft::multiply(p1, p2);
	for(int i=1; i<=n; i++){
		printf("%lld\n", 1ll * w[n+i] * invf[i] % mod);
	}
}