1708. How Many Different Ways Through the Pipeline

A DIRECTED graph with n vertices and m arrows has NO directed cycle. Print how many distinct routes lead from vertex 1 to vertex n, reduced modulo 1000000007. Two routes are distinct when they use a different sequence of arrows.

diamond 1->2, 1->3, 2->4, 3->4 -> 2 chain 1->2->3->4 -> 1 4 vertices, only 1->2 -> 0 vertex 4 cannot be reached 1 vertex, no arrows -> 1 the route that goes nowhere

The last line is the boundary worth settling before writing anything: when n = 1 the start and the target are the same vertex and the empty route counts, so the answer is 1 and not 0.

## The three things that have to be said

directed? yes. self-loops? impossible: a self-loop is a cycle and the input is acyclic. parallel arrows? allowed, and TWO COPIES ARE TWO ROUTES. A route is a sequence of arrows, so using the first copy of 1->3 and using the second are different routes. disconnected? allowed, and only the piece containing vertex 1 contributes.

## What most people try first

Walk every route and count the arrivals. It is obviously correct, it is what the expected answers here were checked against, and it takes as long as the answer is large. The declared case of 48 vertices where each points at the next two has 2971215073 routes, so enumeration there is already hopeless, and the limits allow far worse.

## One number per vertex

Let f[v] be the number of routes from vertex 1 to v. A route to v is a route to some predecessor u followed by the arrow u -> v, and different predecessors or different arrows give different routes, so

f[1] = 1 f[v] = sum over arrows u -> v of f[u]

Fill it in a topological order, so every f[u] is final when it is read. Kahn's algorithm gives the order and performs the additions in the same pass: when a vertex is popped, every arrow into it has already been used.

The answer is f[n].

## Why the parallel-arrow rule is a real decision and not a detail

If routes were counted as sequences of VERTICES, two copies of 1->3 would be one route and the recurrence above would be wrong: it adds f[1] twice. Since the statement counts sequences of ARROWS, adding once per arrow in the input is exactly right, and no deduplication should happen anywhere. The 3 2 test with 1 3 listed twice answers 2 and pins this down.

## Why the modulus is not optional

Route counts in a DAG grow like a product over the layers. A graph of 48 vertices where vertex i points at i + 1 and i + 2 has a Fibonacci number of routes, 2971215073 at n = 48, already past the 2147483647 a signed 32 bit integer holds. At n = 200000 the count has tens of thousands of digits. So the problem asks for the count modulo 1000000007, and every addition is reduced. Because 1000000007 < 2^30, a sum of two reduced values is below 2^31 and stays inside a 32 bit signed integer, but there is no margin for a third addition, so reduce after each one or accumulate in 64 bits.

## Cost

Time O(n + m). Space O(n + m) for the adjacency list; the constraints make an adjacency matrix impossible at 4 * 10^10 entries.

## Related

Problem 1705 counts TOPOLOGICAL ORDERS of a DAG, which is exponential work in n and limited to 16 vertices. Counting routes is linear, and the difference is that a route is built one arrow at a time from a single predecessor while an order depends on the whole set placed so far.

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ m ≤ 200000` - `1 ≤ u, v ≤ n` - the graph has no directed cycle, so no self-loop can occur - the same arrow may be listed more than once, and each copy is a different route - the graph may be disconnected - the answer is to be printed modulo `1000000007`