Một đất nước gồm \(n\) thành phố là một cây. Một quốc gia chọn một thủ đô và một số thành phố phụ thuộc. Với mỗi thành phố phụ thuộc, đường từ thủ đô đến thành phố đó không được đi qua bất kỳ thành phố phụ thuộc nào khác. Với từng \(k\), hãy đếm số quốc gia khác nhau có đúng \(k\) thành phố, modulo \(10^9+7\). Hai lựa chọn khác nhau nếu khác thủ đô hoặc khác ít nhất một thành phố phụ thuộc.

Dữ liệu vào

Dòng đầu chứa \(n\) (\(1\le n\le3000\)). \(n-1\) dòng sau chứa cạnh \(u,v\) (\(1\le u,v\le n\), \(u\ne v\)) của cây. Khoảng cách giữa mọi cặp thành phố trong dữ liệu chính thức nhỏ hơn \(36\) cạnh.

Dữ liệu ra

In \(n\) số: số quốc gia hợp lệ có kích thước từ \(1\) đến \(n\), theo modulo \(10^9+7\).

Ràng buộc

Các giới hạn chính thức của dữ liệu được nêu đầy đủ trong phần Dữ liệu vào.

Phân nhóm

1. \(18\) điểm: \(n\le15\).
2. \(17\) điểm: \(n\le200\).
3. \(26\) điểm: \(n\le600\).
4. \(49\) điểm: không có ràng buộc thêm.

Ví dụ

4
1 2
1 3
1 4

4 12 6 1

4
1 2
2 3
1 4

4 12 4 0

Nguồn

COCI 2025/2026 - Vòng 3, bài Drzava.

Đề bài, dữ liệu kiểm thử và lời giải tham khảo được lấy từ nguồn chính thức của Croatian Open Competition in Informatics.