P1958 Route to School

The streets in your city form a grid, with $a$ north–south streets and $b$ east–west streets. The $a$ north–south streets are numbered from west to east as $1$ to $a$, and the $b$ east–west streets are numbered from south to north as $1$ to $b$. The intersection of north–south street $i$ and east–west street $j$ is denoted as $(i,j)$. You live at $(1,1)$, and the school is at $(a,b)$. You ride a bicycle to school, which can travel only along the streets, and to minimize time you are only allowed to move east or north. Now $N$ intersections are under construction, $(X_1, Y_1)$, $(X_2, Y_2)$, …, $(X_N, Y_N)$, and these intersections are closed to traffic. How many different routes are there to go to school?

The first line contains two integers $a$ and $b$, with $1 \le a, b \le 16$. It is guaranteed that the school is not at $(1,1)$, and that the destination is reachable. The second line contains an integer $N$, indicating that there are $N$ intersections under construction ($1 \le N \le 40$). The next $N$ lines each contain two integers $X_i, Y_i$, giving the locations of the closed intersections.

Output a single integer, the total number of routes from $(1,1)$ to $(a,b)$.

Translated by ChatGPT 5