## Bad Paths

View as PDFI am currently travelling across a tree with vertices.

A simple path between two distinct vertices is called *good* if every edge in the path belongs to the tree. All other simple paths between two distinct vertices are called *bad* because they contain an edge not found in the tree.

For optimization purposes, I have a plan to create an edge between every pair of vertices, if they are not already directly connected. Since edges are expensive, I will base this decision on the number of **distinct** bad paths. In other words, how many new paths would be created? Please help me calculate this number modulo .

**Note:** A simple path does not visit the same vertex twice. Two simple paths are considered **distinct** iff there is an edge in one path that is not used in the other path.

**Note 2:** The exact structure of the tree is irrelevant.

#### Constraints

For all cases:

No will appear twice in the same test case.

Subtask | Points | |
---|---|---|

1 | 20 | |

2 | 30 | |

3 | 50 |

#### Input Specification

The first line contains the integer .

lines of input follow. The line contains .

#### Output Specification

For each , output the number of bad paths modulo .

#### Sample Input

```
2
2
3
```

#### Sample Output

```
0
3
```

Report an issue

## Comments