Chữ ký

"Tùng tùng tùng...".

Trong buổi học cuối cùng của một năm học đầy kỷ niệm, cô giáo chủ nhiệm muốn tạo ra một món quà nhỏ để ghi nhớ lớp học thân thương. Cô nảy ra một ý tưởng: phát một tờ giấy trắng để tất cả học sinh trong lớp cùng ký tên, tạo thành một kỷ vật đáng nhớ.

Cô xếp \(N\) học sinh ngồi theo hình vòng tròn, được đánh số từ \(1\) đến \(N\) theo chiều kim đồng hồ. Sau đó, cô phát một tờ giấy cho một học sinh bất kỳ và yêu cầu bạn ấy ký tên lên đó. Tờ giấy sau đó được truyền đi giữa các học sinh theo quy tắc sau:

• Tờ giấy có thể được chuyền cho học sinh bên trái hoặc bên phải của học sinh đang nắm giữ tờ giấy.
• Ngoài ra, mỗi học sinh còn có thể chọn chuyền tờ giấy cho một học sinh khác là một trong những người bạn thân của họ. Cô giáo được biết trong lớp có \(N-3\) cặp bạn thân và cô đã cố tính sắp xếp, sao cho không có một cặp bạn thân ngồi liền kề, và nếu ta vẽ các đường nối giữa họ trên mặt phẳng, thì không có hai đường nào cắt nhau (ngoại trừ tại các đầu mút). Xem hình minh họa.

Mỗi học sinh chỉ ký tên đúng một lần. Quy trình sẽ kết thúc khi học sinh đầu tiên ký nhận lại tờ giấy, và tạo thành một vòng tuần hoàn khép kín gồm các chữ ký. Lưu ý, ta không tính các tập hợp chữ ký có lực lượng nhỏ hơn 3.

Hai tập hợp chữ ký được xem là khác nhau nếu tồn tại một chữ ký chỉ thuộc một trong hai tập hợp.

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) \((1 \leq N \leq 2 \cdot 10^5)\) --- số học sinh trong lớp.
• Mỗi dòng trong số \(N - 3\) dòng tiếp theo chứa hai số nguyên \(X_i, Y_i\) \((1 \leq X_i, Y_i \leq N)\) --- là một cặp bạn thân.

Output

In ra một số nguyên --- số tập hợp chữ ký khác nhau mà cô giáo có thể nhận được, lấy phần dư theo \(10^9 + 7\).

Example

5
1 3
3 5

6

6
2 4
4 6
6 2

11

Scoring

\begintabularc c l
\hline
Subtask & Điểm & Ràng buộc

\hline
1 & 13 & \(N \leq 15\)

2 & 18 & \(N \leq 300\)

3 & 34 & \(N \leq 2000\)

4 & 15 & Luôn có cặp bạn thân giữa học sinh \(1\) và \(k\) với mọi \(k = 3, 4, \dots, N - 1\)

5 & 40 & Không có ràng buộc bổ sung

\hline
\endtabular