Busy Beaver lại gây náo loạn tại chợ nông sản! Lần này, cậu ấy bắt đầu một cuộc chiến đồ ăn giữa các gian hàng.

Các gian hàng được đánh số từ $1$ đến $N$ và được kết nối bởi $N - 1$ con đường, tạo thành một cây. Nói cách khác, có thể đi từ bất kỳ gian hàng nào đến bất kỳ gian hàng nào khác bằng cách đi theo các con đường, và có duy nhất một đường đi đơn giữa hai gian hàng bất kỳ.

Busy Beaver gán mỗi gian hàng cho Đội Khoai tây (Team Potato) hoặc Đội Cà chua (Team Tomato) như sau:

• Cậu ấy bắt đầu tại gian hàng $1$, đi dọc theo các con đường, ghé thăm mọi gian hàng, và cuối cùng quay trở lại gian hàng $1$. Trong tất cả các lộ trình như vậy, cậu ấy chọn một lộ trình có tổng số con đường đi qua là nhỏ nhất có thể.
• Gian hàng $1$ được gán cho Đội Khoai tây.
• Mỗi khi Busy Beaver ghé thăm một gian hàng lần đầu tiên (ngoại trừ gian hàng $1$), cậu ấy ngay lập tức gán nó cho một trong hai đội. Để giữ sự công bằng cho cuộc chiến, cậu ấy luân phiên việc gán đội mỗi khi gán một gian hàng mới. Nghĩa là, nếu gian hàng được gán gần nhất thuộc về Đội Khoai tây, thì gian hàng mới được ghé thăm tiếp theo phải được gán cho Đội Cà chua, và ngược lại.

Nhiệm vụ của bạn là đếm số lượng cách gán đội có thể xảy ra. Lưu ý rằng các lộ trình có độ dài tối thiểu khác nhau có thể tạo ra cùng một kết quả gán đội cuối cùng; các cách gán như vậy chỉ nên được tính một lần. 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 duy nhất $T$ ($1 \le T \le 10^4$) — số lượng bộ dữ liệu. Dòng đầu tiên của mỗi bộ dữ liệu chứa một số nguyên duy nhất $N$ ($2 \le N \le 10^5$). Mỗi dòng trong $N - 1$ dòng tiếp theo chứa hai số nguyên $u$ và $v$ ($1 \le u, v \le N, u \neq v$), cho biết có một con đường giữa gian hàng $u$ và $v$. Tổng của $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 cách gán đội có thể xảy ra theo modulo $10^9 + 7$.

Nhiệm vụ con

Có ba nhiệm vụ con cho bài toán này:

• (10 điểm): Các gian hàng tạo thành một đồ thị hình sao có gốc tại gian hàng $1$. Cụ thể hơn, gian hàng $1$ có $N - 1$ con đường kết nối với nó.
• (20 điểm): Các gian hàng tạo thành một cây nhị phân có gốc tại gian hàng $1$. Cụ thể hơn, gian hàng $1$ có tối đa $2$ con đường kết nối với nó, và mọi gian hàng khác có tối đa $3$ con đường kết nối với nó.
• (70 điểm): Không có ràng buộc bổ sung.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

2
20
8
12

Ghi chú

Mẫu bao gồm 4 bộ dữ liệu:

• Bộ dữ liệu 1 thỏa mãn nhiệm vụ con thứ hai (cây nhị phân).
• Bộ dữ liệu 2 thỏa mãn nhiệm vụ con thứ nhất (đồ thị hình sao).
• Bộ dữ liệu 3 thỏa mãn nhiệm vụ con thứ hai (cây nhị phân).
• Bộ dữ liệu 4 thỏa mãn nhiệm vụ con thứ ba (không có ràng buộc bổ sung).

Trong bộ dữ liệu đầu tiên, một cách gán đội có thể xảy ra được hiển thị dưới đây.

Một lộ trình có độ dài tối thiểu là: $1 \to 2 \to 3 \to 2 \to 4 \to 2 \to 1$.

Tổng độ dài của nó là $6$, đây là độ dài nhỏ nhất có thể cho một lộ trình bắt đầu tại gian hàng $1$, ghé thăm mọi gian hàng và quay trở lại gian hàng $1$.

Các gian hàng sau đó được gán theo thứ tự chúng được ghé thăm lần đầu tiên:

• Gian hàng $1$ được gán cho Đội Khoai tây.
• Gian hàng $2$ được gán cho Đội Cà chua.
• Gian hàng $3$ được gán cho Đội Khoai tây.
• Gian hàng $4$ được gán cho Đội Cà chua.

Cách gán đội khả thi khác đạt được bằng cách ghé thăm gian hàng $4$ trước gian hàng $3$, điều này làm hoán đổi đội của chúng. Do đó, tổng số cách gán đội có thể xảy ra là $2$.