405641: GYM102020 H Hyperpath

Diogo is quite a guy. Someone that scares people around the Informatics Center, specially Mendes. One day, Mendes gave him a graph challenge, since Diogo claims to be the Graph Theory Master. Just like Math Masters are challenged to solve large multiplications using only the brain, the challenge received by the Graph Theory Master was as follows:

"Given an undirected graph, without multiple edges or self loops, and two arbitrary vertices $$$u$$$ and $$$v$$$. You must build a path from $$$u$$$ to $$$v$$$ with length $$$K$$$ and yell that path out loud without a single mistake."

Anxious to get his revenge, and since there can be many different valid paths, Diogo swore to haunt Mendes' dreams, reciting one different path every night, so that he never doubted his algorithmic skills ever again. In order for Mendes to see what is coming after him, you must write a program that answers for how many nights he won't be able to sleep in peace, i.e in how many distinct paths there are that satisfy the restrictions above. Since this number can be very large, output its remainder on the division by $$$D$$$, on a desperate attempt of relieving Mendes of this terrible burden. If Diogo is not able to build even a single set, your program must print "Mendes will sleep in peace." (without quotes)

P.S.:

1. It is possible to have repetitions of vertices and/or edges in a path.
2. The length of a path is the number of edges in it.

The first line consists of three integers $$$N$$$, $$$M$$$ e $$$D$$$ ($$$1 \le N \le 10^2$$$, $$$0 \le M \le \frac{N(N - 1)}{2}$$$, $$$100 \le D \le 10^9+7$$$), the number of nodes in the graph, the number of edges in the graph and the divisor that should be utilized to print the answer, respectively.

The second line consists of three integers $$$K$$$, $$$u$$$ e $$$v$$$ ($$$0 \le K \le 10^{18}$$$, $$$0 \le u, v < N$$$), the path length, the beginning and the ending of the path that you should find.

Then, $$$M$$$ lines follow describing the graph edges, where the $$$i$$$-th of them contains two integers $$$u_i$$$, $$$v_i$$$ ($$$0 \le u_i, v_i < N$$$, $$$u_i \neq v_i$$$), describing the that there is an edge between vertex $$$u_i$$$ and $$$v_i$$$.

Your program must output a single integer, the number of distinct ways Diogo can build a path of length $$$K$$$ between the two given vertexes, modulo $$$D$$$. If he can't build even a single set, your program must output "Mendes will sleep in peace." (without quotes).

5 5 10000
2 0 4
0 1
1 2
2 3
1 3
3 4

Mendes will sleep in peace.

3 3 10009
3 0 1
0 1
2 0
1 2

3

3 1 100
2 0 0
0 1

1