\(N\) con bò của Đoàn xiếc Nông dân John (\(1 \leq N \leq 10^5\)) đang chuẩn bị cho những tiết mục sắp tới. Tất cả các tiết mục diễn ra trên một cây có các đỉnh được đánh số \(1 \ldots N\). "Trạng thái bắt đầu" của một tiết mục được xác định bởi một số \(1 \leq K \leq N\) và một cách gán các con bò \(1 \ldots K\) vào các đỉnh của cây sao cho không có hai con bò nào ở cùng một đỉnh.

Trong một tiết mục, những con bò thực hiện một số lượng "nước đi" lớn tùy ý. Trong một nước đi, một con bò di chuyển từ đỉnh hiện tại của nó sang một đỉnh kề chưa có con bò nào chiếm giữ. Hai trạng thái bắt đầu được gọi là tương đương nếu có thể đi từ trạng thái này đến trạng thái kia bằng một chuỗi nước đi nào đó.

Với mỗi \(1 \leq K \leq N\), hãy giúp những con bò xác định số lớp tương đương của các trạng thái bắt đầu; nói cách khác, đó là số trạng thái bắt đầu tối đa mà chúng có thể chọn sao cho không có hai trạng thái nào tương đương. Vì những số này có thể rất lớn, hãy in phần dư của chúng theo modulo \(10^9+7\).

Dữ liệu vào

Tệp circus.in:

Dòng \(1\) chứa \(N\).

Mỗi dòng \(2 \leq i \leq N\) chứa hai số nguyên \(a_i\) và \(b_i\), biểu thị một cạnh nối \(a_i\) và \(b_i\) trên cây.

Dữ liệu ra

Tệp circus.out:

Với mỗi \(1 \leq i \leq N\), dòng thứ \(i\) của dữ liệu ra chứa đáp án cho \(K=i\) theo modulo \(10^9+7\).

Phân nhóm

• Các test 3–4 thỏa mãn \(N \leq 8\).
• Các test 5–7 thỏa mãn \(N \leq 16\).
• Các test 8–10 thỏa mãn \(N \leq 100\) và cây có dạng một "ngôi sao"; nhiều nhất một đỉnh có bậc lớn hơn hai.
• Các test 11–15 thỏa mãn \(N \leq 100\).
• Các test 16–20 không có ràng buộc bổ sung.

Ví dụ

5
1 2
2 3
3 4
3 5

1
1
3
24
120

8
1 3
2 3
3 4
4 5
5 6
6 7
6 8

1
1
1
6
30
180
5040
40320

Nguồn

USACO 2020 US Open Contest, Platinum — Circus

Tác giả bài: Dhruv Rohatgi.