#2058. ARBORE

Mitrut có số tự nhiên và một cây có đỉnh. Cậu thắc mắc rằng có bao nhiêu cách để đặt số khác nhau vào cây, mỗi số trên một nút thỏa mản rằng số ở nút nhỏ hơn số của tất cả các nút là con của . Gốc của cây luôn là nút .

Do kết quả có thể rất lớn nên bạn chỉ cần tìm số dư khi chia kết quả tìm được với .

Dữ liệu vào:

• Dòng đầu tiên ghi số ;
• dòng tiếp theo, mỗi dòng ghi hai số nguyên và , thể hiện có một cạnh nối giữa hai đỉnh và .

Dữ liệu ra:

• Ghi ra một số nguyên duy nhất là kết quả cần tính.

Giới hạn:

• số test có ;
• số test có .

Ví dụ:

Dữ liệu vào:

5
1 2
3 1
2 4
2 5

Dữ liệu ra:

8

Giải thích:

• Với ví dụ trên, các cách để đánh số là: