Câu 3. Gấu trúc

Trong khu bảo tồn thiên nhiên X có một khu vực nuôi gấu trúc bao gồm n chuồng được đánh số từ 1 đến n. Có n - 1 cầu nối giữa các chuồng với nhau, cầu nối thứ i (1 ≤ i ≤ n - 1) nối giữa chuồng xi và yi. Các cầu nối được bố trí sao cho từ một chuồng bất kì đều có thể di chuyển đến các chuồng còn lại. Với mỗi cặp chuồng v và w (1 ≤ v, w ≤ n), ta định nghĩa khoảng cách giữa v và w là số lượng cầu nối trên đường di chuyển từ v đến w, kí hiệu là d(v, w).

Trong mỗi chuồng có duy nhất một chú gấu trúc đang ở. Mỗi ngày, người chăm sóc sẽ đưa ra lịch trình di chuyển cho các chú gấu trúc như sau:

• Đầu tiên, chọn tuỳ ý một hoán vị p = (p1, p2, ..., pn) của các chuồng (1, 2, ..., n).
• Sau đó, với mỗi i (1 ≤ i ≤ n), chú gấu trúc đang ở chuồng i sẽ di chuyển tới chuồng pi. Trong quá trình di chuyển, để cho các chú gấu trúc có nhiều thời gian gần gũi hơn với thiên nhiên, người chăm sóc sẽ chọn ra lịch trình sao cho tổng khoảng cách mà các chú gấu trúc cần phải di chuyển là lớn nhất. Cụ thể, người chăm sóc sẽ chọn hoán vị p sao cho tổng khoảng cách T = d(1, p1) + d(2, p2) + ... + d(n, pn) là lớn nhất.

Yêu cầu: Hãy giúp người chăm sóc tìm số cách để chọn hoán vị p thỏa mãn T là lớn nhất. Kết quả chia lấy dư cho (1000000009+7).

Dữ liệu vào: Cho trong file văn bản GAUTRUC.INP, có cấu trúc như sau:

• Dòng 1: Ghi số nguyên dương n (2 ≤ n ≤ 5000).

• Dòng thứ i trong n - 1 dòng tiếp theo: Mỗi dòng ghi hai số nguyên dương xi, yi mô tả một cầu nối giữa hai chuồng (1 ≤ i ≤ n – 1; 1 ≤ xi, yi ≤ n).
• Các số trên một dòng được ghi cách nhau ít nhất một dấu cách. Dữ liệu vào luôn đảm bảo tính hợp lệ.

Kết quả: Ghi ra file văn bản GAUTRUC.OUT, có cấu trúc như sau:

• Dòng 1: Ghi một số nguyên là kết quả cần tìm.

Ràng buộc:

• Có 10% số lượng test ứng với 10% số điểm có n ≤ 10;
• Có 40% số lượng test ứng với 40% số điểm có 10 < n ≤ 500;
• Có 50% số lượng test ứng với 50% số điểm có 500 < n ≤ 5000. Ví dụ:

GAUTRUC.INP

3

1 2

2 3

GAUTRUC.OUT

3

Giải thích: Tổng khoảng cách lớn nhất là 4. Có 3 cách chọn p là (2, 3, 1), (3, 1, 2), (3, 2, 1).