Robot dọn dẹp

Thị trấn ICPC có $N$ ngã tư được đánh số từ $1$ đến $N$, nối với nhau bởi $N-1$ con đường sao cho từ một ngã tư bất kỳ luôn đi được tới mọi ngã tư khác.

Chính quyền muốn triển khai một đội robot dọn dẹp. Mỗi robot $k$ được giao một nhiệm vụ là tập ngã tư $T_k$ mà nó phải dọn, với $|T_k|\ge 1$. Kế hoạch triển khai phải thỏa mãn:

• Mỗi tập $T_k$ tạo thành một đường đi: tồn tại dãy $v_1,v_2,\dots ,v_{|T_k|}$ gồm đúng các phần tử đôi một khác nhau của $T_k$, trong đó hai ngã tư liên tiếp được nối trực tiếp bởi một con đường.
• Hợp của tất cả các $T_k$ là toàn bộ tập ngã tư của thị trấn.
• Hai robot khác nhau không cùng dọn một ngã tư, tức $T_i\cap T_j=\varnothing$ với mọi $i\ne j$.
• Kế hoạch không rút gọn được: không tồn tại hai robot $i\ne j$ sao cho $T_i\cup T_j$ cũng tạo thành một đường đi.

Chính quyền không quan tâm số robot được dùng có ít nhất hay không, miễn là kế hoạch thỏa mãn cả bốn điều kiện trên.

Hãy đếm số kế hoạch triển khai hợp lệ. Hai kế hoạch được coi là khác nhau nếu chúng khác nhau ở tập hợp các nhiệm vụ (thứ tự các robot không quan trọng). Vì kết quả có thể rất lớn, hãy in ra phần dư của nó khi chia cho ${10}^9+7$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $N$ là số ngã tư.
• $N-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u_i$ và $v_i$ mô tả con đường nối ngã tư $u_i$ và ngã tư $v_i$.

Dữ liệu ra

In ra một số nguyên duy nhất là số kế hoạch triển khai hợp lệ, lấy phần dư khi chia cho ${10}^9+7$.

Ràng buộc

• $1\le N\le 100000$
• $1\le u_i<v_i\le N$
• Dữ liệu đảm bảo các con đường tạo thành một cây (từ mỗi ngã tư đều đi được tới mọi ngã tư khác).

Ví dụ