Lưu ý: Giới hạn bộ nhớ của bài này là 512MB, gấp đôi mức mặc định.

Một cây nhị phân hoàn hảo là một cây có gốc mà mỗi đỉnh không phải lá có đúng hai đỉnh con và tất cả các đỉnh lá cách gốc một khoảng bằng nhau.

Một cây nhị phân hoàn hảo không gốc là một cây không gốc mà khi chọn một trong các đỉnh của nó làm gốc, cây đó trở thành một cây nhị phân hoàn hảo.

Bessie có một cây gồm \(N\) đỉnh (\(1\le N\le 10^5\)). Hãy xác định số cách xóa một tập con các cạnh khỏi cây sao cho rừng thu được là một tập hợp các cây nhị phân hoàn hảo không gốc. Vì đáp án có thể rất lớn, hãy in kết quả lấy modulo \(10^9+7\).

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên \(T\) (\(1\leq T\leq 100\)), là số bộ test độc lập.

Dòng đầu tiên của mỗi bộ test chứa một số nguyên \(N\).

Mỗi dòng trong \(N-1\) dòng tiếp theo của mỗi bộ test chứa hai số nguyên \(u_i\) và \(v_i\) (\(1\leq u_i,v_i\leq N\)), biểu thị một cạnh nối hai đỉnh \(u_i\) và \(v_i\).

Đảm bảo rằng trong mỗi bộ test, các cạnh đã cho tạo thành một cây gồm \(N\) đỉnh.

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

Dữ liệu ra

Với mỗi bộ test, in ra một số nguyên duy nhất: số tập con các cạnh mà khi bị xóa sẽ tạo ra một rừng là tập hợp các cây nhị phân hoàn hảo không gốc, lấy modulo \(10^9+7\).

Ví dụ

3
6
1 2
3 2
4 6
5 6
6 2
3
1 2
3 2
7
2 1
2 3
1 6
1 7
3 4
3 5

8
2
14

Phân nhóm

• Inputs 2-3: \(N\le 15\).
• Inputs 4-5: Không đỉnh nào kề với nhiều hơn hai đỉnh khác.
• Inputs 6-9: \(N\le 1000\), tổng \(N\) không vượt quá \(2000\), và không đỉnh nào kề với nhiều hơn ba đỉnh khác.
• Inputs 10-13: Không đỉnh nào kề với nhiều hơn ba đỉnh khác.
• Inputs 14-21: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 US Open, Open Division — Perfect Binary Trees. Tác giả: Avnith Vijayram.
https://usaco.org/index.php?page=viewproblem2&cpid=1604