One fine morning you discovered yourself standing in a maze. The maze can be considered a connected weighted undirected graph. You are currently standing in vertex and to get out of the maze you need to go to vertex . But there’s a catch. In order to get out of the maze you need to choose a path from to such that, the path length differs from the shortest path length of to by at-most . You are wondering how many ways are there to solve the maze.
More formally, count the number of paths from to in a connected weighted undirected graph such that, the path length differs from the shortest path length of to by at-most .
As the answer can be huge, you need to print it modulo .
A path is a sequence of vertices such that there exists an undirected edge for .
Two paths differ, if they contain different number of vertices or there is an index , where the edge differs.
A path can visit the same vertex multiple times and even the initial vertex and final vertex can be visited multiple times. It is only required that you start at vertex and finish at vertex and maintain the path length constraint.
The graph doesn’t contain multi-edges and self loops.
The first line of the input contains a single integer — the number of test cases.
The first line of each test case contains three integers and — the number of vertices, the number of edges and the path length constraint.
The next line contains two integers and — the initial vertex and final vertex.
The following lines describe the edges. Each contains three integers — the undirected edge and the weight of the edge.
It is guaranteed that there is at most one edge between any pair of vertices in the graph and the given graph is connected.
The sum of and the sum of over all testcases doesn't exceed .
For each testcase, print a single integer — the number of paths modulo .
Input | Output |
---|---|
2 6 7 1 1 6 1 2 1 2 3 1 3 4 1 4 5 1 5 6 1 3 5 2 2 4 3 7 10 6 1 7 1 2 1 2 3 1 3 4 1 4 5 1 5 6 1 6 7 1 2 5 2 3 5 2 4 6 3 5 7 4 | 3 332 |
Consider the first test case, and . Shortest path length from to is . Maximum allowed path length is . Total three paths possible. . Length . . Length . . Length . |