There are n intersections labeled 0 through n - 1. Each entry [u, v, time] in roads gives a bidirectional road that takes time minutes to traverse. The network is connected, and no two intersections have more than one road between them.
Return the number of different routes from intersection 0 to intersection n - 1 that achieve the shortest possible travel time. Return the count modulo 1000000007.
Routes are different when their sequences of intersections differ. When n == 1, staying at intersection 0 is one route of travel time zero.
Example 1:
Input: n = 4
roads = [[0,1,2],[0,2,2],[1,3,3],[2,3,3]]
Output: 2Explanation: The routes 0 → 1 → 3 and 0 → 2 → 3 both take 5 minutes. No shorter route exists, so there are 2 shortest routes.
Example 2:
Input: n = 3
roads = [[0,1,2],[1,2,2],[0,2,7]]
Output: 1Explanation: The route 0 → 1 → 2 takes 4 minutes, while the direct road takes 7. Exactly one route achieves the minimum travel time.
Example 3:
Input: n = 1
roads = []
Output: 1Explanation: The starting intersection and destination are both 0. Staying there is one route with travel time zero.
Constraints:
1 <= n <= 200n - 1 <= roads.length <= n * (n - 1) / 2roads[i].length == 3- Road endpoints are distinct labels between
0andn - 1. 1 <= time <= 1000000000- No pair of intersections has more than one road.
- Every intersection is reachable from every other intersection.