Giả sử hàm \(\text{randint}(l,r)\) trả về một số nguyên được chọn độc lập và đồng đều ngẫu nhiên trong đoạn \([l,r]\).

Bessie sinh một cây ngẫu nhiên có nhãn gồm \(N\) đỉnh (\(2\le N\le 2\cdot 10^5\)) bằng quy trình hai bước sau:

1. Bắt đầu với các đỉnh được gán nhãn từ \(1\) đến \(N\). Với mỗi \(i\) từ \(2\) đến \(N\), thêm một cạnh nối đỉnh \(i\) với đỉnh \(\text{randint}(1,i-1)\).
2. Chọn đồng đều ngẫu nhiên một hoán vị \(p_1,p_2,\dots,p_N\) của \(\{1,2,\ldots,N\}\). Gán lại nhãn của mỗi đỉnh \(v\) thành \(p_v\).

Bây giờ, Farmer John quan sát tập cạnh của cây cuối cùng và muốn biết xác suất để quy trình hai bước trên sinh ra một cây có tập cạnh chính xác là tập cạnh này. Bạn có thể xác định xác suất đó theo modulo \(10^9+7\) không?

Dữ liệu vào

Dữ liệu vào gồm \(T\) (\(1\le T\le 10\)) bộ test độc lập. Mỗi bộ test được mô tả như sau:

Dòng đầu tiên chứa \(N\).

\(N-1\) dòng tiếp theo chứa các cạnh của cây, mỗi cạnh được mô tả bởi hai số nguyên \(u\) và \(v\) cách nhau bởi dấu cách (\(1\le u,v\le N\)). Dữ liệu đảm bảo các cạnh này tạo thành một cây.

Tổng \(N\) trên tất cả các bộ test không vượt quá \(5\cdot 10^5\).

Dữ liệu ra

Với mỗi bộ test, in xác suất theo modulo \(10^9+7\) trên một dòng mới (lưu ý rằng xác suất cần in là một tỉ số của hai số nguyên, vì vậy bạn cần in kết quả của phép chia này khi tính theo modulo \(10^9+7\)).

Ví dụ

4
2
2 1
3
1 2
2 3
4
1 2
2 3
2 4
4
1 2
2 3
3 4

1
333333336
83333334
55555556

Phân nhóm

• Inputs 2-3: \(N\le 8\).
• Inputs 4-9: \(N\le 2000\).
• Inputs 10-21: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 Contest 3, Gold Division — bài gốc tiếng Anh “Random Tree Generation”. Tác giả: Benjamin Qi. https://usaco.org/index.php?page=viewproblem2&cpid=1595