Gánh Xiếc

Sân khấu của gánh xiếc là một cây gồm $N$ đỉnh, đánh số từ $1$ đến $N$.

Với một số $K$ cho trước ($1\le K\le N$), một trạng thái là cách đặt $K$ con bò được đánh số từ $1$ đến $K$ vào $K$ đỉnh phân biệt của cây, mỗi đỉnh nhiều nhất một con bò. Các con bò là phân biệt: đổi chỗ hai con bò cho nhau tạo ra một trạng thái khác.

Một bước di chuyển là chọn một con bò và đưa nó sang một đỉnh kề đang trống. Hai trạng thái được gọi là tương đương nếu từ trạng thái này có thể đi tới trạng thái kia sau một số hữu hạn bước di chuyển.

Với mỗi $K$ từ $1$ đến $N$, hãy đếm số lớp tương đương của các trạng thái ứng với $K$ con bò. Vì kết quả có thể rất lớn, in ra phần dư khi chia cho ${10}^9+7$.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $N$.
• $N-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u$ và $v$ ($1\le u,v\le N$) mô tả một cạnh của cây.

Dữ liệu ra

In ra $N$ dòng. Dòng thứ $K$ chứa số lớp tương đương ứng với $K$ con bò, lấy phần dư cho ${10}^9+7$.

Ràng buộc

• $1\le N\le {10}^5$
• Dữ liệu vào luôn mô tả một cây.

Ví dụ