There are n cities numbered 1..n and a list of one-way flights (a, b). Count the routes that start in city 1, end in city n, and visit every city exactly once. Return the count modulo 10**9 + 7.
Write count_routes(n: int, flights: list[tuple[int, int]]) -> int.
- Flights are directed. The same flight may appear more than once; each copy counts as a different way to fly that leg, so it multiplies the number of routes.
- Constraints:
2 <= n <= 16, up to a few thousand flights.
count_routes(4, [(1, 2), (2, 3), (3, 4), (1, 3), (3, 2), (2, 4)])
# 2: 1-2-3-4 and 1-3-2-4
count_routes(3, [(1, 2), (1, 2), (2, 3)])
# 2: the two copies of 1->2 give two different routes
count_routes(3, [(1, 3), (3, 2)])
# 0: every route must end at city 3
Enumerating paths one by one is hopeless on dense graphs: a complete graph on 16 cities has billions of routes. Aim for about O(2^n · n²).
Show hint
Two partial routes that have visited the same set of cities and stand at the same city can be finished in exactly the same ways, so count them together. City n may only be entered last.