I 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
Comments