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<cstdlib>
#include<algorithm>
#define maxn 1000005
#define mod 924844033
using namespace std;
const int G=5;
int omega[maxn],N=1,n;
inline int add(int a,int b){a+=b; return a>=mod?a-mod:a;}
inline int sub(int a,int b){a-=b; return a<0?a+mod:a;}
int ksm(int a,int b){int s=1;for(;b;a=1ll*a*a%mod,b>>=1) if(b&1) s=1ll*s*a%mod; return s;}
int fac[maxn],facinv[maxn],cnt[maxn];
void NTT(int *A,int n,int type)
{
    int t0,t1;
    for(int i=0,j=0;i<n;i++)
    {
        if(i<j) swap(A[i],A[j]);
        for(int k=(n>>1);(j^=k)<k;k>>=1);
    }
    omega[0]=1;
    for(int m=1;m<n;m<<=1)
    {
        t0=ksm(G,(mod-1+type*(mod-1)/(m<<1))%(mod-1));
        for(int i=1;i<m;i++) omega[i]=1ll*omega[i-1]*t0%mod;
        for(int k=0;k<n;k+=(m<<1))
        {
            for(int i=k;i<k+m;i++)
            {
                t0=A[i];
                t1=1ll*A[i+m]*omega[i-k]%mod;
                A[i]=add(t0,t1),A[i+m]=sub(t0,t1);
            }
        }
    }
    if(type==1) return;
    t0=ksm(n,mod-2);
    for(int i=0;i<n;i++) A[i]=1ll*A[i]*t0%mod;
}
int t0[maxn],t1[maxn];
void Mul(int *A,int *B,int *C)
{
    for(int i=0;i<N;i++) t0[i]=A[i],t1[i]=B[i];
    NTT(t0,N,1),NTT(t1,N,1);
    for(int i=0;i<N;i++) t0[i]=1ll*t0[i]*t1[i]%mod;
    NTT(t0,N,-1);
    for(int i=0;i<N;i++) C[i]=t0[i];
}
int pre[maxn],las[maxn],to[maxn],sz[maxn],inc;
void ins(int a,int b){pre[++inc]=las[a],las[a]=inc,to[inc]=b;}
void dfs(int x,int f)
{
    sz[x]=1;
    for(int i=las[x];i;i=pre[i])
    {
        if(to[i]==f) continue;
        dfs(to[i],x),sz[x]+=sz[to[i]];
    }
    if(x!=1) cnt[sz[x]]++,cnt[n-sz[x]]++;
}
int cc[maxn];
int main()
{
    scanf("%d",&n);
    fac[0]=facinv[0]=1;
    for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod,facinv[i]=ksm(fac[i],mod-2);
    for(int i=1;i<=n;i++) cc[i]=1ll*fac[n]*facinv[i]%mod*facinv[n-i]%mod*n%mod;
    for(int i=1,u,v;i<n;i++) scanf("%d%d",&u,&v),ins(u,v),ins(v,u);
    dfs(1,0);
    for(int i=0;i<=n;i++) fac[i]=1ll*fac[i]*cnt[i]%mod;
    reverse(facinv,facinv+n+1);
    while(N<=2*n) N<<=1;
    Mul(fac,facinv,fac);
    reverse(facinv,facinv+n+1);
    for(int i=1;i<=n;i++)
        printf("%d\n",sub(cc[i],1ll*facinv[i]*fac[i+n]%mod));
    return 0;
}