n junctions numbered 1 to n, joined by two-way roads: roads[i] = [u, v, w] is a road of length w between junctions u and v. Every junction can reach every other one.
The depot is at junction n. For every junction x, let d(x) be the length of the shortest path from x to the depot.
A courier leaves junction 1 for the depot with one quirk: after driving along any road, they must end up strictly closer to the depot than before. In other words, a route x₀ = 1, x₁, ..., x_k = n counts if d(xᵢ) > d(xᵢ₊₁) at every step.
Count such routes. The number can be huge, so return it modulo 10⁹ + 7.n=4, roads=[[1, 2, 2], [2, 4, 1], [1, 3, 1], [3, 4, 3], [2, 3, 1]] → 3
Shortest distances to the depot at 4 are 1 for junction 2, 2 for junction 3 and 3 for junction 1. The routes 1 → 2 → 4, 1 → 3 → 4 and 1 → 3 → 2 → 4 all qualify: every step strictly reduces the distance to the depot.
n=3, roads=[[1, 2, 1], [2, 3, 1], [1, 3, 5]] → 2
Distances are 1 for junction 2 and 2 for junction 1. You can drive straight 1 → 3 or go through 2, so there are 2 routes.
n=2, roads=[[1, 2, 7]] → 1
n=4, roads=[[1, 2, 2], [2, 4, 1], [1, 3, 1], [3, 4, 3], [2, 3, 1]]
3
Run checks the first 3 tests in your browser. Submit checks all 42 tests on the server, hidden ones included.