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.

-----Sample Input-----
4 4
1 3
1 2 1
2 3 1
3 4 1
4 1 1

-----Sample Output-----
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.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'mod=10**9+7\n\nclass Dijkstra():\n    """ ダイクストラ法\n    重み付きグラフにおける単一始点最短路アルゴリズム\n\n    * 使用条件\n        - 負のコストがないこと\n        - 有向グラフ、無向グラフともにOK\n\n    * 計算量はO(E*log(V))\n\n    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい\n    """\n    class Edge():\n        """ 重み付き有向辺 """\n        def __init__(self, _to, _cost):\n            self.to = _to\n            self.cost = _cost\n\n    def __init__(self, V):\n        """ 重み付き有向辺\n        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい\n\n        Args:\n            V(int): 頂点の数\n        """\n        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺\n        self._E = 0  # 辺の数\n        self._V = V  # 頂点の数\n\n    @property\n    def E(self):\n        """ 辺数\n        無向グラフのときは、辺数は有向グラフの倍になる\n        """\n        return self._E\n\n    @property\n    def V(self):\n        """ 頂点数 """\n        return self._V\n\n    def add(self, _from, _to, _cost):\n        """ 2頂点と、辺のコストを追加する """\n        self.G[_from].append(self.Edge(_to, _cost))\n        self._E += 1\n\n    def edge(self,_from):\n        return self.G[_from]\n\n    def shortest_path(self, s):\n        """ 始点sから頂点iまでの最短路を格納したリストを返す\n        Args:\n            s(int): 始点s\n        Returns:\n            d(list): d[i] := 始点sから頂点iまでの最短コストを格納したリスト。\n                     到達不可の場合、値はfloat("inf")\n        """\n        import heapq\n        que = []  # プライオリティキュー（ヒープ木）\n        d = [10**15] * self.V\n        d[s] = 0\n        cnt=[0]*self.V\n        cnt[s]=1\n        heapq.heappush(que, (0, s))  # 始点の(最短距離, 頂点番号)をヒープに追加する\n\n        while len(que) != 0:\n            cost, v = heapq.heappop(que)\n            # キューに格納されている最短経路の候補がdの距離よりも大きければ、他の経路で最短経路が存在するので、処理をスキップ\n            if d[v] < cost: continue\n\n            for i in range(len(self.G[v])):\n                # 頂点vに隣接する各頂点に関して、頂点vを経由した場合の距離を計算し、今までの距離(d)よりも小さければ更新する\n                e = self.G[v][i]  # vのi個目の隣接辺e\n                if d[e.to] > d[v] + e.cost:\n                    d[e.to] = d[v] + e.cost  # dの更新\n                    heapq.heappush(que, (d[e.to], e.to))  # キューに新たな最短経路の候補(最短距離, 頂点番号)の情報をpush\n                    cnt[e.to]=cnt[v]%mod\n                elif d[e.to]==d[v]+e.cost:\n                    cnt[e.to]+=cnt[v]\n                    cnt[e.to]%=mod\n        return d,cnt\n\nimport sys\n\ninput=sys.stdin.readline\nsys.setrecursionlimit(1000000)\n\nN,M=list(map(int,input().split()))\nS,T=list(map(int,input().split()))\nmati=Dijkstra(N)\nfor i in range(M):\n    u,v,d=list(map(int,input().split()))\n    mati.add(u-1,v-1,d)\n    mati.add(v-1,u-1,d)\n\nspath,Sways=mati.shortest_path(S-1)\ntpath,Tways=mati.shortest_path(T-1)\n\nans=Sways[T-1]*Tways[S-1]\nans%=mod\nfor u in range(N):\n    for e in mati.edge(u):\n        v=e.to\n        d=e.cost\n        ans-=(Tways[v]*Sways[u])**2*(spath[u]+d+tpath[v]==spath[T-1] and spath[u]+d!=tpath[v] and spath[u]!=tpath[v]+d and (tpath[v]+d>=spath[u]>=tpath[v] or tpath[v]+d>=spath[u]+d>=tpath[v]))\n        ans%=mod\n\nfor i in range(N):\n    ans-=(Tways[i]*Sways[i])**2*(spath[i]+tpath[i]==spath[T-1] and spath[i]==tpath[i])\n    ans%=mod\n\nprint((ans%mod))\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 21739