Description

Cece loves visiting the park. The park can be regarded as a directed graph with $N$ vertices and $M$ edges, without self-loops and without multiple edges. Vertex $1$ is the entrance and vertex $N$ is the exit. Each edge has a non-negative weight representing the time Cece spends to traverse that edge.

Cece visits the park every day. He always enters from vertex $1$ and exits at vertex $N$.

Cece likes new things. He does not want to take exactly the same route on two different days. He also does not want to spend too much time. If the shortest path length from vertex $1$ to vertex $N$ is $d$, then Cece only likes routes with length no more than $d + K$.

Cece wants to know how many routes satisfy these conditions. Can you help him?

To avoid large output, report the answer modulo $P$.

If there are infinitely many valid routes, output $-1$.

Input Format

The first line contains an integer $T$, the number of test cases.

Then follow $T$ test cases. For each test case:

• The first line contains four integers $N, M, K, P$, separated by a single space.
• The next $M$ lines each contain three integers $a_i, b_i, c_i$, indicating there is a directed edge from vertex $a_i$ to vertex $b_i$ with weight $c_i$, with integers separated by a single space.

Output Format

The output contains $T$ lines, each with one integer representing the answer.

2
5 7 2 10
1 2 1
2 4 0
4 5 2
2 3 2
3 4 1
3 5 2
1 5 3
2 2 0 10
1 2 0
2 1 0

3
-1

Hint

[Sample Explanation 1]

For the first test case, the shortest distance is $3$. $1\to 5, 1\to 2\to 4\to 5, 1\to 2\to 3\to 5$ are $3$ valid paths.

[Testdata and Conventions]

For different test points, the scales of various parameters do not exceed the following.

::cute-table{tuack}

For $100\%$ of the testdata, $1 \le P \le 10^9$, $1 \le a_i, b_i \le N$, $0 \le c_i \le 1000$.

The testdata guarantees that at least one valid route exists.

• 2019.8.30 Added a set of hack testdata by @skicean.
• 2022.7.21 Added a set of hack testdata by @djwj233.

Translated by ChatGPT 5