## DMOPC '21 Contest 9 P6 - Shortest Paths

View as PDF

Points: 30 (partial)
Time limit: 2.5s
Memory limit: 256M

Author:
Problem types

Let the value of a connected undirected graph be the length of the shortest path from to . Compute the sum of the values of all connected simple graphs with vertices and edges of length for each . Since the answers may be very large, output them modulo the prime .

#### Constraints

is prime.

##### Subtask 4 [20%]

No additional constraints.

#### Input Specification

The first and only line contains integers , , and .

#### Output Specification

On a single line, output the desired values modulo .

#### Sample Input 1

3 3 100000007

#### Sample Output 1

4 1

#### Explanation for Sample 1

There are three graphs with nodes and edges. One has a value of , and two have a value of . There is one graph with nodes and edges, and it has a value of .

#### Sample Input 2

4 6 100000007

#### Sample Output 2

26 20 7 1

## Comments

There are no comments at the moment.