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_i$. The time it takes to traverse this edge is $D_i$ minutes, regardless of direction and who traverses the edge (Takahashi or Aoki).

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 \leq N \leq 100$ $000$
• $1 \leq M \leq 200$ $000$
• $1 \leq S, T \leq N$
• $S \neq T$
• $1 \leq U_i, V_i \leq N$ ($1 \leq i \leq M$)
• $1 \leq D_i \leq 10^9$ ($1 \leq i \leq M$)
• If $i \neq j$, then $(U_i, V_i) \neq (U_j, V_j)$ and $(U_i, V_i) \neq (V_j, U_j)$.
• $U_i \neq V_i$ ($1 \leq i \leq M$)
• $D_i$ are integers.
• The given graph is connected.

Input

Input is given from Standard Input in the following format:

N M
S T
U_1 V_1 D_1
U_2 V_2 D_2
:
U_M V_M D_M

Output

Print the answer.