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:
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using std::min;
using std::max;
using std::swap;
using std::vector;
typedef double db;
typedef long long ll;
#define pb(A) push_back(A)
#define pii std::pair<int,int>
#define all(A) A.begin(),A.end()
#define mp(A,B) std::make_pair(A,B)
const int N=8e5+5;
const int mod=924844033;

int fac[N],ifac[N];
int n,m,cnt,head[N],buc[N];
int a[N],b[N],sze[N],lim,rev[N];

struct Edge{
    int to,nxt;
}edge[N<<1];

void add(int x,int y){
    edge[++cnt].to=y;
    edge[cnt].nxt=head[x];
    head[x]=cnt;
}

int ksm(int a,int b=mod-2,int ans=1){
    while(b){
        if(b&1) ans=1ll*ans*a%mod;
        a=1ll*a*a%mod;b>>=1;
    } return ans;
}

void ntt(int *f,int opt){
    for(int i=1;i<lim;i++) if(i<rev[i]) swap(f[i],f[rev[i]]);
    for(int mid=1;mid<lim;mid<<=1){
        int tmp=ksm(5,(mod-1)/(mid<<1));
        if(opt<0) tmp=ksm(tmp);
        for(int R=mid<<1,j=0;j<lim;j+=R){
            for(int w=1,k=0;k<mid;k++,w=1ll*w*tmp%mod){
                int x=f[j+k],y=1ll*f[j+k+mid]*w%mod;
                f[j+k]=(x+y)%mod;f[j+k+mid]=(mod+x-y)%mod;
            }
        }
    } if(opt<0) 
        for(int in=ksm(lim),i=0;i<lim;i++) f[i]=1ll*f[i]*in%mod;
}

void dfs(int now){
    sze[now]=1; buc[n]++;
    for(int i=head[now];i;i=edge[i].nxt){
        int to=edge[i].to;
        if(sze[to]) continue;
        dfs(to); sze[now]+=sze[to]; buc[sze[to]]--;
    } buc[n-sze[now]]--;
}

int getint(){
    int X=0,w=0;char ch=getchar();
    while(!isdigit(ch))w|=ch=='-',ch=getchar();
    while( isdigit(ch))X=X*10+ch-48,ch=getchar();
    if(w) return -X;return X;
}

void init(int n){
    fac[0]=ifac[0]=1;
    for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
    ifac[n]=ksm(fac[n]);
    for(int i=n-1;i;i--) ifac[i]=1ll*ifac[i+1]*(i+1)%mod;
}

signed main(){
    n=getint();init(N-5);
    for(int i=1;i<n;i++){
        int x=getint(),y=getint();
        add(x,y),add(y,x);
    } dfs(1);
    lim=1;while(lim<=n+n) lim<<=1;
    for(int i=1;i<lim;i++) rev[i]=(rev[i>>1]>>1)|(i&1?lim>>1:0);
    for(int i=0;i<=n;i++)
        a[n-i]=1ll*(buc[i]+mod)*fac[i]%mod,
        b[i]=ifac[i];
    ntt(a,1),ntt(b,1);
    for(int i=0;i<lim;i++) a[i]=1ll*a[i]*b[i]%mod;
    ntt(a,-1);
    for(int i=1;i<=n;i++) printf("%lld\n",1ll*a[n-i]%mod*ifac[i]%mod);
    return 0;
}