1073. Number of Ways to Arrive at Destination

Given a connected undirected weighted graph with n nodes and edges [u, v, w], return the number of distinct shortest paths from node 0 to node n-1, modulo 1000000007. The input is JSON {n, edges}.

Input: JSON {n, edges} with edges [u, v, w].

Output: Integer — the count of shortest paths, modulo 1e9+7.

Examples

Input: {"n":7,"edges":[[0,6,7],[0,1,2],[1,2,3],[1,3,3],[6,3,3],[3,5,1],[6,5,1],[2,5,1],[0,4,5],[4,6,2]]}
Output: 4
Explanation: Four shortest paths of equal length.

Input: {"n":2,"edges":[[0,1,5]]}
Output: 1
Explanation: One path.

Input: {"n":1,"edges":[]}
Output: 1
Explanation: Source equals destination.

Constraints

• 1<=n<=200
• connected
• w>=1

Asked by