$N$ con bò của đoàn xiếc Farmer John ($1 \leq N \leq 10^5$) đang chuẩn bị cho các 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 ban đầ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 đặt các con bò $1\dots K$ lên 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, các con bò thực hiện một số lượng “bước di chuyển” lớn tùy ý. Trong một bước di chuyển, một con bò đi từ đỉnh hiện tại của mình đến một đỉnh kề chưa có bò. Hai trạng thái ban đầu được gọi là tương đương nếu có thể đạt được trạng thái này từ trạng thái kia bằng một dãy bước di chuyển nào đó.

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

Dữ liệu vào

Dòng $1$ chứa $N$.

Các dòng $2\le i\le N$ mỗi dòng chứa hai số nguyên $a_i$ và $b_i$, biểu thị một cạnh nối $a_i$ với $b_i$ trong cây.

Dữ liệu ra

Với mỗi $1\le i\le N,$ dòng thứ $i$ của dữ liệu ra phải chứa đáp án cho $K=i$ lấy phần dư khi chia cho $10^9+7$.

Ví dụ

Dữ liệu vào 1

5
1 2
2 3
3 4
3 5

Dữ liệu ra 1

1
1
3
24
120

Ghi chú

Với $K=1$ và $K=2,$ hai trạng thái bất kỳ đều có thể biến đổi thành nhau.

Bây giờ xét $K=3$, và gọi $c_i$ là vị trí của con bò $i$. Trạng thái $(c_1,c_2,c_3)=(1,2,3)$ tương đương với các trạng thái $(1,2,5)$ và $(1,3,2).$ Tuy nhiên, nó không tương đương với trạng thái $(2,1,3).$

Dữ liệu vào 2

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

Dữ liệu ra 2

1
1
1
6
30
180
5040
40320

Nhiệm vụ con

• Các test 3–4 thỏa mãn $N\le 8.$
• Các test 5–7 thỏa mãn $N\le 16.$
• Các test 8–10 thỏa mãn $N\le 100$ và cây tạo thành một “ngôi sao”; có 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\le 100$.
• Các test 16–20 không có giới hạn bổ sung.

Tác giả bài toán: Dhruv Rohatgi