Zbunjenost

Ο κύριος Μάλναρ αποφάσισε να περάσει το καλοκαίρι του ταξιδεύοντας τον κόσμο, πετώντας σε τυχαία μέρη. Μετά από κάποιο διάστημα, βρέθηκε στην πρωτεύουσα μιας άγνωστης χώρας, όπου οι δρόμοι του θύμιζαν μια τριγωνοποίηση! Πιο συγκεκριμένα, η πόλη αποτελείται από ~N~ ενδιαφέρουσες τοποθεσίες, αριθμημένες από ~1~ έως ~N~, που συνδέονται από ~2N-3~ δρόμους. Οι τοποθεσίες ~1~, ~2~, ~...~, ~N~ είναι συνδεδεμένες με αυτήν την σειρά για να σχηματίσουν ένα κυρτό πολύγωνο με ~N~ πλευρές. Οι υπόλοιποι ~N-3~ δρόμοι συνδέουν τις τοποθεσίες με τέτοιο τρόπο ώστε να μην υπάρχει ζέυγος δρόμων που να διασταυρώνονται, εκτός ίσως από τα άκρα τους.

Καθώς περπατούσε στους δρόμους της πρωτεύουσας αυτής της χώρας, ο κύριος Μάλναρ βρέθηκε στην τοποθεσία από όπου ξεκίνησε, χωρίς να επισκεφτεί καμιά τοποθεσία περισσότερες από μία φορά. Λίγο μπερδεμένος, συνειδητοποίησε ότι αυτό είναι απόλυτα φυσιολογικό και σκέφτηκε έναν τρόπο μέτρησης της σύγχυσής του, ως τον αριθμό των απλών κλειστών βρόχων. Ένας απλός κλειστός περίπατος είναι μια ακολουθία σημείων (τοποθεσιών) ~V_1~, ~V_2~, ~...~, ~V_m~, τέτοια ώστε το ~V_i~ να είναι συνδεδεμένο μέσω δρόμου με το ~V_{i+1}~ για κάθε ~i = 1, 2, ..., m-1~ και το ~V_m~ να είναι συνδεδεμένο με το ~V_1~. Δύο περίπατοι θεωρούνται ισοδύναμοι αν ο ένας μπορεί να προκύψει από μια κυκλική περιστροφή του άλλου ή από μια αντιστροφή του άλλου. Για παράδειγμα, ο περίπατος ~(1,\;2,\;3,\;4)~ είναι ισοδύναμος με τον περίπατο ~(2,\;3,\;4,\;1)~. Απλός κλειστός βρόχος είναι ένα σύνολο ισοδύναμων περιπάτων.

Ο κύριος Μάλναρ τώρα ζητά τη βοήθειά σας για να υπολογίσετε το βάθμο σύγχυσης που προκαλεί αυτή η πόλη!

Είσοδος

Στην πρώτη γραμμή θα βρίσκεται ένας ακέραιος ~N\;(1 \le N \le 2*10^5)~, ο αριθμός των ενδιαφερουσών τοποθεσιών.

Στις επόμενες ~N-3~ γραμμές θα βρίσκονται οι ακέραιοι ~X_i~, ~Y_i\;(1 \le X_i,\;Y_i \le N)~, οι ετικέτες των τοποθεσιών που συνδέονται από τον ~i~-οστό δρόμο.

Έξοδος

Στην πρώτη και μοναδική γραμμή εκτυπώστε το βάθμο σύγχυσης της δεδομένης πόλης modulo ~10^9 + 7~.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
~1~	~13~	~N \le 15~
~2~	~18~	~N \le 300~
~3~	~34~	~N \le 2000~
~4~	~15~	Τα σημεία ~1~ και ~k~ είναι συνδεδεμένα, για όλα τα ~k = 3, 4, ..., N-1~
~5~	~40~	Κανένας επιπλέον περιορισμός.

Παραδείγματα

1ο

input

4
1 3

output

3

Επεξήγηση του πρώτου παραδείγματος:

Στο σχέδιο, κάθε βρόχος έχει χρωματιστεί με διαφορετικό χρώμα.

2ο

input

5
1 3
3 5

output

6

Επεξήγηση του δεύτερου παραδείγματος:

Οι περίπατοι που αντιπροσωπεύουν βρόχους είναι: ~(1,\;2,\;3)~, ~(1,\;3,\;5)~, ~(3,\;4,\;5)~, ~(1,\;2,\;3,\;5)~, ~(1,\;3,\;4,\;5)~, ~(1,\;2,\;3,\;4,\;5)~.

3ο

input

6
2 4
4 6
6 2

output

11

Επεξήγηση του τρίτου παραδείγματος:

Οι περίπατοι που αντιπροσωπεύουν βρόχους είναι: ~(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)~.