zbunjenost (COCI CONTEST_#1)
Time limit: 5 seconds | Memory limit: 512 MB | Task type: batch
Algorithms: tree dp

# Task Zbunjenost

Mr. Malnar decided to spend his summer traveling around the world by flying randomly. After some time, he found himself in an unknown country's capital where streets reminded him of a triangulation! More precisely, the city consists of *N* interesting locations numbered from 1 to *N* connected by 2*N* − 3 streets. Locations 1, 2, ..., *N* are connected in that order to form a convex polygon with *N* sides. Remaining *N* − 3 streets connect locations in such a way that no two streets cross, except maybe at their ends.

While walking the streets of this country's capital Mr. Malnar found himself at the location where he started from without visiting any location more than once. A bit confused he came to the realization that this is completely normal and came up with a measure of confusion as the number of simple closed loops. Simple closed walk is a sequence of locations *V*<sub>1</sub>, *V*<sub>2</sub>, ..., *V*<sub>m</sub> such that *V*<sub>i</sub> is connected via street with location *V*<sub>i+1</sub> for every *i* = 1, 2, ..., *m* − 1 and that location *V*<sub>m</sub> is connected with *V*<sub>1</sub>. Two walks are equivalent if one can be obtained by a cyclic rotation of the other, or by reversing the other. For example, walk (1, 2, 3, 4) is equivalent to the walk (2, 3, 4, 1). Simple closed loop is a set of equivalent walks. Mr. Malnar now asks for your help in calculating the confusion of this city!

## Input

In the first line is an integer *N* (1 ≤ *N* ≤ 2 ⋅ 10<sup>5</sup>), number of interesting locations.

In the next *N* − 3 lines are integers *X<sub>i</sub>*, *Y<sub>i</sub>* (1 ≤ *X<sub>i</sub>, Y<sub>i</sub>* ≤ *N*), labels of locations connected by the *i*-th street.

## Output

In the first and only line output the confusion of the given city modulo 10<sup>9</sup> + 7.

## Scoring

| Subtask | Points | Constraints                                                 |
| :------: | :----: | :---------------------------------------------------------- |
|    1     |   13   | *N* ≤ 15                                                    |
|    2     |   18   | *N* ≤ 300                                                   |
|    3     |   34   | *N* ≤ 2000                                                  |
|    4     |   15   | Locations 1 and k are connected for all k = 3, 4, ..., N − 1. |
|    5     |   40   | No additional constraints.                                  |

## Examples

| Input | Input | Input |
| :---: | :---: | :---: |
|   4   |   5   |   6   |
|  1 3  |  1 3  |  2 4  |
|       |  3 5  |  4 6  |
|       |       |  6 2  |
| Output | Output | Output |
|   3   |   6   |  11   |

![](_page_1_Picture_0.jpeg)

### Clarification of the first example:

On the sketch, each loop is colored in a different color.

![](_page_1_Figure_5.jpeg)

#### Clarification of the second example:

Walks that represent loops are: (1, 2, 3), (1, 3, 5), (3, 4, 5), (1, 2, 3, 5), (1, 3, 4, 5), (1, 2, 3, 4, 5).

#### Clarification of the third example:

Walks that represent loops are: (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).

Starter code:

Grader code:

Setup script:

Evaluation script: