#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

### Title

### Problem Statement

We have a graph with `N` vertices and `M` edges, and there are two people on the graph: Takahashi and Aoki.

The `i`-th edge connects Vertex `U _{i}` and Vertex

`V`. The time it takes to traverse this edge is

_{i}`D`minutes, regardless of direction and who traverses the edge (Takahashi or Aoki).

_{i}Takahashi departs Vertex `S` and Aoki departs Vertex `T` at the same time. Takahashi travels to Vertex `T` and Aoki travels to Vertex `S`, both in the shortest time possible.
Find the number of the pairs of ways for Takahashi and Aoki to choose their shortest paths such that they never meet (at a vertex or on an edge) during the travel, modulo `10 ^{9} + 7`.

### Constraints

`1 ≤ N ≤ 100``000``1 ≤ M ≤ 200``000``1 ≤ S, T ≤ N``S ≠ T``1 ≤ U`(_{i}, V_{i}≤ N`1 ≤ i ≤ M`)`1 ≤ D`(_{i}≤ 10^{9}`1 ≤ i ≤ M`)- If
`i ≠ j`, then`(U`and_{i}, V_{i}) ≠ (U_{j}, V_{j})`(U`._{i}, V_{i}) ≠ (V_{j}, U_{j}) `U`(_{i}≠ V_{i}`1 ≤ i ≤ M`)`D`are integers._{i}- The given graph is connected.

### Input

Input is given from Standard Input in the following format:

NMSTU_{1}V_{1}D_{1}U_{2}V_{2}D_{2}:U_{M}V_{M}D_{M}

### Output

Print the answer.

### Sample Input 1

4 4 1 3 1 2 1 2 3 1 3 4 1 4 1 1

### Sample Output 1

2

There are two ways to choose shortest paths that satisfies the condition:

- Takahashi chooses the path
`1 \rightarrow 2 \rightarrow 3`, and Aoki chooses the path`3 \rightarrow 4 \rightarrow 1`. - Takahashi chooses the path
`1 \rightarrow 4 \rightarrow 3`, and Aoki chooses the path`3 \rightarrow 2 \rightarrow 1`.

### Sample Input 2

3 3 1 3 1 2 1 2 3 1 3 1 2

### Sample Output 2

2

### Sample Input 3

3 3 1 3 1 2 1 2 3 1 3 1 2

### Sample Output 3

2

### Sample Input 4

8 13 4 2 7 3 9 6 2 3 1 6 4 7 6 9 3 8 9 1 2 2 2 8 12 8 6 9 2 5 5 4 2 18 5 3 7 5 1 515371567 4 8 6

### Sample Output 4

6

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 100 | 18 | 1s | 256MB | Minimum |

2 | 0 | 4 | 1s | 256MB | Minimum |

### Judge Compile Command

g++-8 ans.cpp -o avoidcollision -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512