3. Visiting the Park

(park.cpp/c/pas)

Cece loves visiting the park. The park can be viewed as a directed graph with $N$ nodes and $M$ edges, containing no self-loops or multiple edges. Node 1 is the entrance to the park, and node $N$ is the exit. Each edge has a non-negative weight, representing the time it takes for Cece to traverse that edge.

Cece visits the park every day, entering from node 1 and exiting from node $N$.

Cece likes novel things; he does not want to take the exact same route through the park on any two days. At the same time, Cece is a student who loves to study, and he does not want to spend too much time in the park each day. If the shortest path length from node 1 to node $N$ is $d$, then Cece will only like routes with a length not exceeding $d + K$.

Cece wants to know how many such routes satisfy the condition. Can you help him?

To avoid excessively large outputs, the answer should be taken modulo $P$.

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

Input

The input file is named park.in.

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

For each test case: The first line contains four integers $N, M, K, P$, with each integer separated by a space.

The following $M$ lines each contain three integers $a_i, b_i, c_i$, representing a directed edge from node $a_i$ to node $b_i$ with weight $c_i$, with each integer separated by a space.

Output

The output file is named park.out.

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

Examples

Input 1

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

Output 1

3
-1

Note

See park/park1.in and park/park1.ans in the contestant directory. For the first test case, the shortest path is 3. The paths $1 \to 5$, $1 \to 2 \to 4 \to 5$, and $1 \to 2 \to 3 \to 5$ are the 3 valid routes.

Input 2

(See park/park2.in in the contestant directory)

Output 2

(See park/park2.ans in the contestant directory)

Constraints

For different test cases, the constraints on the parameters are as follows:

For 100% of the data, $1 \le P \le 10^9$, $1 \le a_i, b_i \le N$, $0 \le c_i \le 1000$. Guarantee: At least one valid route exists.