F. Graph Problem
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a connected weighted graph with $$$n$$$ vertices and $$$m$$$ bidirectional edges. You are to traverse from vertex $$$s$$$ to vertex $$$t$$$.

Across all (not necessarily simple) paths from $$$s$$$ to $$$t$$$, count the number of distinct sums of weights along those paths modulo $$$k$$$.

Input

The first line contains the number of test cases $$$T$$$ ($$$1\leq T \leq 10$$$). The description of the test cases follows.

The first line of each test case contains five space-separated integers, $$$n$$$, $$$m$$$, $$$k$$$, $$$s$$$, and $$$t$$$ ($$$1 \leq n \leq 10^5, n-1 \leq m \leq 2 \cdot 10^5, 1 \leq k \leq 10^9$$$, $$$1 \leq s, t \leq n$$$).

The next $$$m$$$ lines of each test case contain three space-separated integers $$$u$$$, $$$v$$$, and $$$w$$$ ($$$1 \leq u, v \leq n, 0 \leq w \leq 10^9$$$), denoting that an edge of weight $$$w$$$ connects vertices $$$u$$$ and $$$v$$$.

It is guaranteed that the given graph is connected.

—

Tests in subtasks are numbered from $$$1−20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.

Tests $$$1-6$$$ satisfy $$$k \leq 10$$$.

Tests $$$7-20$$$ satisfy no additional constraints.

Output

Output one integer $$$-$$$ the number of possible sums of weights modulo $$$k$$$.

Example
Input
1
4 5 3 1 4
1 4 3
1 2 1
2 4 2
2 3 4
3 4 5
Output
3
Note

In the first test case of the sample, $$$k = 3$$$.

The path $$$1 \rightarrow 4$$$ has a sum of weights $$$3 \equiv 0 \mod 3$$$.

The path $$$1 \rightarrow 2 \rightarrow 3 \rightarrow 4$$$ has a sum of weights $$$10 \equiv 1 \mod 3$$$.

The path $$$1 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 4$$$ has a sum of weights $$$5 \equiv 2 \mod 3$$$.

It can be shown that no other distinct sums of weights modulo $$$3$$$ can be achieved.

—

Problem Idea: culver0412

Problem Preparation: Ryan Fu

Occurrences: Novice K / Advanced F