Lưu ý: Giới hạn bộ nhớ cho bài toán này là 512MB, gấp đôi so với 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 nút không phải là lá đều có đúng hai nút con và tất cả các nút lá đều cách gốc một khoảng cách 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 nút bất kỳ làm gốc, nó trở thành một cây nhị phân hoàn hảo.

Bessie có một cây với $N$ ($1 \le N \le 10^5$) nút. Hãy xác định số cách loại bỏ một tập hợp 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ì kết quả có thể rất lớn, hãy in ra kết quả theo 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$), số lượng bộ dữ liệu kiểm thử độc lập.

Dòng đầu tiên của mỗi bộ dữ liệu 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ộ dữ liệu 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 giữa hai nút $u_i$ và $v_i$.

Đảm bảo rằng với mỗi bộ dữ liệu, các cạnh đã cho tạo thành một cây có $N$ nút.

Ngoài ra, tổng $N$ trên tất cả các bộ dữ liệu không vượt quá $2\cdot 10^5$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một số nguyên duy nhất: số lượng tập hợp các cạnh mà khi loại bỏ sẽ tạo thành một rừng gồm các cây nhị phân hoàn hảo không gốc, theo modulo $10^9+7$.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

8
2
14

Ghi chú

Trong bộ dữ liệu đầu tiên, Bessie có thể loại bỏ bất kỳ tập hợp cạnh nào sau đây để thu được một rừng các cây nhị phân hoàn hảo:

1. $(2, 6)$
2. $(1, 2)$, $(2, 3)$, $(2, 6)$
3. $(1, 2)$, $(2, 3)$, $(4, 6)$
4. $(1, 2)$, $(2, 3)$, $(5, 6)$
5. $(1, 2)$, $(4, 6)$, $(5, 6)$
6. $(2, 6)$, $(4, 6)$, $(5, 6)$
7. $(2, 3)$, $(4, 6)$, $(5, 6)$
8. $(1, 2)$, $(2, 3)$, $(2, 6)$, $(4, 6)$, $(5, 6)$

Tập hợp thứ nhất tạo ra hai cây con có chiều cao $1$, tập hợp cuối cùng tạo ra sáu cây con có chiều cao $0$, và các tập hợp còn lại tạo ra ba cây con có chiều cao $0$ và một cây con có chiều cao $1$.

Chấm điểm

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

Nguồn bài toán: Avnith Vijayram