@cache
def dfs(root, dest):
    if root == dest:
        return 1
    path_count = 0
    vis.add(root)
    for node, _ in graph[root]:
        if node not in vis and distance[node] > distance[root]:
            path_count+= dfs(node, dest)
    vis.remove(root)
    return path_count
return dfs(n-1, 0)%(10**9+7)