Sinh Cây Ngẫu Nhiên

Bessie tạo cây ngẫu nhiên có nhãn gồm $N$ đỉnh qua hai bước:

Bước 1: Bắt đầu với các đỉnh $1$ đến $N$. Với mỗi $i$ từ $2$ đến $N$, nối đỉnh $i$ với một đỉnh ngẫu nhiên đều trong $\{1,2,\dots ,i-1\}$.

Bước 2: Chọn một hoán vị ngẫu nhiên đều $p_1,p_2,\dots ,p_N$ của $\{1,\dots ,N\}$. Đổi nhãn mỗi đỉnh $v$ thành $p_v$.

Cho tập cạnh cuối cùng, tính xác suất mà quá trình trên sinh ra tập cạnh này. Kết quả modulo ${10}^9+7$.

Dữ liệu vào

• Dòng 1: Số nguyên $T$ — số bộ test ($1\le T\le 10$)
• Với mỗi bộ test:
  • Dòng 1: Số nguyên $N$ ($2\le N\le 2\times {10}^5$)
  • $N-1$ dòng tiếp theo: Hai số nguyên $u,v$ mô tả cạnh

Tổng $N$ trên tất cả bộ test không vượt quá $5\times {10}^5$.

Dữ liệu ra

Với mỗi bộ test, in ra xác suất modulo ${10}^9+7$.

Ràng buộc

• $2\le N\le 2\times {10}^5$
• $\sum N\le 5\times {10}^5$

Ví dụ

Ghi chú

• Test 2-3: $N\le 8$
• Test 4-9: $N\le 2000$
• Test 10-21: Không ràng buộc bổ sung