Waterpark

The local waterpark has a great slide complex, with many paths crisscrossing down the hill. There is one start point and one end point, but at various points you can turn and take different paths. Walter and Wanda wonder exactly how many different ways there are to go down the slide. Can you solve their problem?

More precisely, there are $n$ marked points (including the start at point $1$ and the end at point $n$) where the paths down the hill may split or merge. All paths move down the hill toward higher-numbered points; some paths cross over others without meeting, but we do not have to worry about that, nor about collisions between sliders. The task is simply to determine the number of different sequences of marked points one can follow down the hill.

For example, at one small waterpark there are $4$ points, with direct slides from $1$ to points $2$ and $4$; from $2$ to $3$ and $4$; and from $3$ to $4$. There are $3$ ways down the hill: you can go $(1,2,3,4)$, $(1,2,4)$, or $(1,4)$.

Hint: think about starting from the bottom of the slide.

The first line contains a single integer $n$ ($1 \le n \le 9999$), the number of marked points. Each of the following lines contains a point pair of the form x y, where $1 \le x < y \le n$, indicating a direct slide from point $x$ to point $y$. For example, 1234 8765 indicates a direct slide from point $1234$ to point $8765$. The list ends with the point pair 0 0.

Print a single integer: the number of different paths from point $1$ to point $n$. You may assume this number is less than $2^{30}$. If there is no path from point $1$ to point $n$, the number of paths is $0$.