冤家路窄

题目限制

3000 ms 256 M

题目描述

一个 $n$ 个顶点 $m$ 条边的无向图（顶点编号 $1\sim n$，无重边和自环），通过其每条边都需要一定时间。

小 $A$ 和小 $B$ 是一对冤家，开始时小 $A$ 位于点 $S$ ，小 $B$ 位于点 $T$ 。他们同时出发，分别沿着最短路去往对方所在的点，即小 $A$ 要去往 $T$ 点，小 $B$ 要去往 $S$ 点。

需要你来设计双方的路线，使得他们不会在途中相遇（即在某个时间点上，双方即不在同一个点上，也不在同一条边上）。求符合条件的方案数对 $10^9+7$ 取模的结果。

输入格式

第一行输入两个数n,m，分别表示点数和边数； 第二行输入两个数S,T，分别表示起点和终点的编号； 之后m行，每行3个数u,v,d，表示u,v间有一条边，通过需要d分钟。 其中n≤1e5,m≤2e5,d≤1e9。

输出格式

输出符合条件的方案数对1e9+7 取模的结果。

数据范围

对于20%的数据，$1 \le n \le 10, 1 \le m \le 20$；

对于100%的数据，$1 \le n \le 100000, 1 \le m \le 200000, 1 \le S,T \le n(S \ne T), 1 \le u,v \le n, 1 \le d \le 10^9$。

输入样例

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

输出样例

2