Anh Hạo quyết định dành mùa hè du lịch vòng quanh thế giới bằng cách bay ngẫu nhiên. Sau một thời gian, anh thấy mình ở thủ đô của một quốc gia không rõ, nơi các con đường làm anh nhớ đến một phép tam giác phân! Cụ thể hơn, thành phố bao gồm \(N\) địa điểm thú vị được đánh số từ \(1\) đến \(N\) được kết nối bởi \(2N - 3\) con đường. Các địa điểm \(1, 2, . . ., N\) được kết nối theo thứ tự đó để tạo thành một đa giác lồi với \(N\) cạnh. \(N - 3\) con đường còn lại kết nối các địa điểm sao cho không có hai con đường nào cắt nhau, ngoại trừ có thể tại các đầu mút của chúng.

Trong khi đi bộ trên các con đường của thủ đô quốc gia này, anh Hạo thấy mình ở địa điểm mà anh đã bắt đầu mà không ghé thăm bất kỳ địa điểm nào hơn một lần. Hơi bối rối, anh nhận ra rằng điều này hoàn toàn bình thường và nghĩ ra một thước đo độ bối rối là số lượng vòng lặp kín đơn giản. Đường đi kín đơn giản là một chuỗi các địa điểm \(V_1, V_2, . . ., V_m\) sao cho \(V_i\) được kết nối qua đường phố với địa điểm \(V_{i+1}\) cho mọi \(i = 1, 2, . . . , m - 1\) và địa điểm \(V_m\) được kết nối với \(V_1\). Hai đường đi là tương đương nếu một cái có thể thu được bằng cách xoay vòng cái kia, hoặc bằng cách đảo ngược cái kia. Ví dụ, đường đi \((1, 2, 3, 4)\) tương đương với đường đi \((2, 3, 4, 1)\). Vòng lặp kín đơn giản là một tập hợp các đường đi tương đương. anh Hạo giờ yêu cầu bạn giúp tính độ bối rối của thành phố này!

Dữ liệu vào

• Trong dòng đầu tiên là một số nguyên \(N\) \((1 \le N \le 2 \times 10^5)\), số lượng địa điểm thú vị.
• Trong \(N - 3\) dòng tiếp theo là các số nguyên \(X_i, Y_i\) \((1 \le X_i, Y_i \le N)\), nhãn của các địa điểm được kết nối bởi con đường thứ \(i\).

Dữ liệu ra

• Trong dòng đầu tiên và duy nhất, in ra độ bối rối của thành phố đã cho modulo \(10^9 + 7\).

Chấm điểm

Input 1

4
1 3

Output 1

3

Input 2

5
1 3
3 5

Output 2

6

Input 3

6
2 4
4 6
6 2

Output 3

11

Làm rõ ví dụ đầu tiên: Trên hình vẽ, mỗi vòng lặp được tô một màu khác nhau.

Làm rõ ví dụ thứ hai: Các đường đi biểu diễn vòng lặp là: (1, 2, 3), (1, 3, 5), (3, 4, 5), (1, 2, 3, 5), (1, 3, 4, 5), (1, 2, 3, 4, 5).

Làm rõ ví dụ thứ ba: Các đường đi biểu diễn vòng lặp là: (1, 2, 6), (2, 3, 4), (4, 5, 6), (2, 4, 6), (1, 2, 4, 6), (2, 3, 4, 6), (2, 4, 5, 6), (1, 2, 3, 4, 6), (2, 3, 4, 5, 6), (1, 2, 4, 5, 6), (1, 2, 3, 4, 5, 6).