{"raw_statement":[{"iden":"problem statement","content":"We have a graph with $N$ vertices and $M$ edges, and there are two people on the graph: Takahashi and Aoki.\nThe $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).\nTakahashi 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$."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 100$ $000$\n*   $1 \\leq M \\leq 200$ $000$\n*   $1 \\leq S, T \\leq N$\n*   $S \\neq T$\n*   $1 \\leq U_i, V_i \\leq N$ ($1 \\leq i \\leq M$)\n*   $1 \\leq D_i \\leq 10^9$ ($1 \\leq i \\leq M$)\n*   If $i \\neq j$, then $(U_i, V_i) \\neq (U_j, V_j)$ and $(U_i, V_i) \\neq (V_j, U_j)$.\n*   $U_i \\neq V_i$ ($1 \\leq i \\leq M$)\n*   $D_i$ are integers.\n*   The given graph is connected."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$\n$S$ $T$\n$U_1$ $V_1$ $D_1$\n$U_2$ $V_2$ $D_2$\n$:$\n$U_M$ $V_M$ $D_M$"},{"iden":"sample input 1","content":"4 4\n1 3\n1 2 1\n2 3 1\n3 4 1\n4 1 1"},{"iden":"sample output 1","content":"2\n\nThere are two ways to choose shortest paths that satisfies the condition:\n\n*   Takahashi chooses the path $1 \\rightarrow 2 \\rightarrow 3$, and Aoki chooses the path $3 \\rightarrow 4 \\rightarrow 1$.\n*   Takahashi chooses the path $1 \\rightarrow 4 \\rightarrow 3$, and Aoki chooses the path $3 \\rightarrow 2 \\rightarrow 1$."},{"iden":"sample input 2","content":"3 3\n1 3\n1 2 1\n2 3 1\n3 1 2"},{"iden":"sample output 2","content":"2"},{"iden":"sample input 3","content":"3 3\n1 3\n1 2 1\n2 3 1\n3 1 2"},{"iden":"sample output 3","content":"2"},{"iden":"sample input 4","content":"8 13\n4 2\n7 3 9\n6 2 3\n1 6 4\n7 6 9\n3 8 9\n1 2 2\n2 8 12\n8 6 9\n2 5 5\n4 2 18\n5 3 7\n5 1 515371567\n4 8 6"},{"iden":"sample output 4","content":"6"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}