Limits 5s, 512 MB

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 ss and to get out of the maze you need to go to vertex tt. But there’s a catch. In order to get out of the maze you need to choose a path from ss to tt such that, the path length differs from the shortest path length of ss to tt by at-most kk. You are wondering how many ways are there to solve the maze.

More formally, count the number of paths from ss to tt in a connected weighted undirected graph such that, the path length differs from the shortest path length of ss to tt by at-most kk.

As the answer can be huge, you need to print it modulo 998244353998244353.

A path is a sequence of vertices (v1,v2,v3,,vp)(v_1,v_2,v_3,\ldots,v_p) such that there exists an undirected edge (vi,vi+1)(v_i,v_{i+1}) for i=1,2,,p1i=1,2,\ldots,p-1.

Two paths differ, if they contain different number of vertices or there is an index ii, where the edge (vi,vi+1)(v_i,v_{i+1}) differs.

A path can visit the same vertex multiple times and even the initial vertex ss and final vertex tt can be visited multiple times. It is only required that you start at vertex ss and finish at vertex tt and maintain the path length constraint.

The graph doesn’t contain multi-edges and self loops.

Input

The first line of the input contains a single integer T(1T1000) T(1 \le T \le 1000)— the number of test cases.

The first line of each test case contains three integers n,mn,m and kk(2n2×105,n1m2×105,1k100)(2 \le n \le 2\times10^5, n-1 \le m \le 2\times10^5, 1 \le k \le 100) — the number of vertices, the number of edges and the path length constraint.

The next line contains two integers ss and tt (1s,tn,st)(1 \le s,t \le n, s \ne t)— the initial vertex and final vertex.

The following mm lines describe the edges. Each contains three integers u,v,wu, v, w (1u,vn,uv,1w109)(1 \le u,v \le n, u \ne v, 1 \le w \le 10^9) — the undirected edge (u,v)(u,v) 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 nn and the sum of mm over all testcases doesn't exceed 2×1052\times10^5.

Output

For each testcase, print a single integer — the number of paths modulo 998244353998244353.

Sample

InputOutput
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, s=1,t=6s=1, t=6 and k=1k=1.

Shortest path length from ss to tt is 55. Maximum allowed path length is 5+1=65+1 = 6.

Total three paths possible.

1234561 \to 2 \to 3 \to 4 \to 5 \to 6. Length 55.

123561 \to 2 \to 3 \to 5 \to 6. Length 55.

124561 \to 2 \to 4 \to 5 \to 6. Length 66.


Submit

Login to submit.

Statistics

77% Solution Ratio
ash_98Earliest, Feb '23
PromodFastest, 1.0s
HSTU_TREENITYLightest, 108 MB
ChatGPTShortest, 1508B
Toph uses cookies. By continuing you agree to our Cookie Policy.