问题描述

我们有一个具有$N$个顶点和$M$条边的图，图上有两个人：高桥和青木。

第$i$条边连接顶点$U_i$和顶点$V_i$。不考虑方向和穿越边的人（高桥或青木），穿越这条边需要$D_i$分钟。

高桥从顶点$S$出发，青木从顶点$T$出发，同时出发。高桥前往顶点$T$，青木前往顶点$S$，两者都选择最短时间的路径。计算高桥和青木选择最短路径的对数，使得他们在旅行过程中不会相遇（在顶点或边上），结果取模$10^9 + 7$。

约束条件

• $1 \leq N \leq 100000$
• $1 \leq M \leq 200000$
• $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$)
• 如果 $i \neq j$，则 $(U_i, V_i) \neq (U_j, V_j)$ 和 $(U_i, V_i) \neq (V_j, U_j)$。
• $U_i \neq V_i$ ($1 \leq i \leq M$)
• $D_i$ 是整数。
• 给定的图是连通的。

输入

从标准输入读取输入。数据格式如下：

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

输出

输出答案。

示例输入 1

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

示例输出 1

2

有两种满足条件的最短路径选择方式：

• 高桥选择路径 $1 \rightarrow 2 \rightarrow 3$，青木选择路径 $3 \rightarrow 4 \rightarrow 1$。
• 高桥选择路径 $1 \rightarrow 4 \rightarrow 3$，青木选择路径 $3 \rightarrow 2 \rightarrow 1$。

示例输入 2

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

示例输出 2

2

示例输入 3

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

示例输出 3

2

示例输入 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

示例输出 4

6