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 1 [30%]
Subtask 2 [20%]
Subtask 3 [30%]
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