Ở một vùng đất xa xôi mang tên Airlanvaosma-i có ~n~ thành phố được nối với nhau bằng ~n - 1~ con đường. Từ bất kỳ thành phố nào cũng có thể đi tới bất kỳ thành phố nào khác, và mọi đường đi ngắn nhất đều đi qua ít hơn ~36~ con đường.

Đức vua Krešimir muốn lập ra quốc gia riêng của mình. Mỗi quốc gia phải có đúng ~1~ thủ đô để điều hành, cùng với một số thành phố phụ thuộc, có thể là ~0~. Kích thước của một quốc gia bằng tổng số thành phố thuộc về nó, bao gồm thủ đô và toàn bộ các thành phố phụ thuộc.

Để việc cai trị hiệu quả, Krešimir đặt ra quy tắc sau:

• Với mỗi thành phố phụ thuộc, trên đường đi từ thủ đô tới thành phố đó không được có thêm bất kỳ thành phố phụ thuộc nào khác.

Nói cách khác, không thành phố phụ thuộc nào được nằm giữa thủ đô và một thành phố phụ thuộc khác.

Với mỗi kích thước quốc gia ~k~, trong đó ~1 \le k \le n~, hãy xác định có bao nhiêu quốc gia khác nhau mà Krešimir có thể thành lập. Vì đáp án có thể rất lớn, hãy in các giá trị theo modulo ~10^9 + 7~.

Hai cách chọn quốc gia được coi là khác nhau nếu chúng khác nhau ở thủ đô hoặc khác nhau ở ít nhất ~1~ thành phố phụ thuộc được chọn.

Input

Dòng đầu tiên chứa một số nguyên dương ~n~, với ~1 \le n \le 3000~.

~n - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u~ và ~v~, với ~1 \le u, v \le n~ và ~u \ne v~, biểu thị rằng hai thành phố đó được nối trực tiếp với nhau.

Output

In ra trên một dòng duy nhất ~n~ số nguyên, trong đó số thứ ~k~ là số quốc gia có kích thước ~k~ theo yêu cầu đề bài.

Chấm điểm

• Subtask ~1~ (~18~ điểm): ~1 \le n \le 15~
• Subtask ~2~ (~17~ điểm): ~1 \le n \le 200~
• Subtask ~3~ (~26~ điểm): ~1 \le n \le 600~
• Subtask ~4~ (~49~ điểm): Không có ràng buộc bổ sung.

Sample Input ~1~

4
1 2
1 3
1 4

Sample Output ~1~

4 12 6 1

Sample Input ~2~

4
1 2
2 3
1 4

Sample Output ~2~

4 12 4 0

Giải thích

• Ví dụ ~2~: Có ~4~ quốc gia kích thước ~1~, vì có ~4~ cách chọn thủ đô. Có ~12~ quốc gia kích thước ~2~, vì sau khi chọn thủ đô (~4~ cách), ta chọn thêm ~1~ thành phố phụ thuộc (~3~ cách). Có ~4~ quốc gia kích thước ~3~, vì nếu chọn thủ đô là ~1~ hoặc ~2~ thì mỗi trường hợp có đúng ~2~ cách chọn thêm ~2~ thành phố phụ thuộc.