Gánh Xiếc

Nông dân John đang chuẩn bị biểu diễn gánh xiếc với $N$ con bò, được đánh số từ $1$ đến $N$. Sân khấu gánh xiếc được biểu diễn bởi một cây gồm $N$ đỉnh được đánh số từ $1$ đến $N$.

Một trạng thái khởi đầu cho $K$ con bò ($1\le K\le N$) là cách gán $K$ con bò phân biệt (được đánh số từ $1$ đến $K$) vào $K$ đỉnh phân biệt của cây. Một bước di chuyển là: chọn một con bò và di chuyển nó đến một đỉnh kề chưa bị chiếm. Hai trạng thái được gọi là tương đương nếu có thể đến được từ trạng thái này sang trạng thái kia bằng 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 khởi đầu cho $K$ con bò. In kết quả modulo ${10}^9+7$.

Dữ liệu vào

• Dòng $1$: Số nguyên $N$ — số đỉnh của cây.
• $N-1$ dòng tiếp theo: Mỗi dòng gồm 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 $N$ dòng. Dòng $K$ là số lớp tương đương cho $K$ con bò, modulo ${10}^9+7$.

Ràng buộc

• $1\le N\le {10}^5$

Ví dụ

Ghi chú

• Hai con bò được coi là phân biệt (có đánh số), nên việc hoán đổi vị trí của hai con bò tạo ra trạng thái khác.
• Khi $K=N$: tất cả $N!$ trạng thái đều thuộc các lớp tương đương khác nhau (mỗi trạng thái là một lớp riêng).
• Khi $K$ nhỏ (nhiều đỉnh trống), các con bò có thể di chuyển tự do và tất cả trạng thái về cơ bản là tương đương.