Counting Limited Park Routes

In this problem, you are given a directed graph with N vertices and M edges without self-loops or multiple edges. Vertex 1 is the entrance of the park and vertex N is the exit. Each edge has a non‐negative weight representing the time cost to traverse that edge.

Every day, a person enters the park at vertex 1 and leaves at vertex N. He does not want to take the same route on two different days. Moreover, if the shortest time from vertex 1 to vertex N is denoted by \(d\) (in latex: \(d\)), he will only consider a route if its total time is at most \(d+K\), where \(K\) is a given integer. Your task is to count the number of distinct routes from 1 to N with total time \(\ell\) satisfying \(\ell \le d+K\). Since the answer can be very large, output the result modulo \(P\). If there are infinitely many valid routes, output \(-1\) instead.

Note on infinite routes: A potential source of infinitely many routes is the existence of a cycle whose total weight is zero. If such a zero‐cost cycle is reachable from vertex 1 and can reach vertex N without increasing the accumulated cost beyond \(d+K\), then infinitely many distinct routes can be generated by traversing the cycle arbitrarily many times.

inputFormat

The first line contains four integers \(N\), \(M\), \(K\), and \(P\) where \(N\) is the number of vertices, \(M\) is the number of edges, \(K\) is the allowed extra time compared to the shortest path, and \(P\) is the modulus.

Each of the following \(M\) lines contains three integers \(u\), \(v\), and \(w\) indicating a directed edge from vertex \(u\) to vertex \(v\) with non-negative weight \(w\>.

outputFormat

Output a single integer representing the number of distinct routes from 1 to \(N\) whose total time is at most \(d+K\) (where \(d\) is the shortest time from 1 to \(N\)), modulo \(P\). If there are infinitely many such routes, output \(-1\).

sample

3 3 1 100
1 2 1
2 3 1
1 3 3

2