Commute Route

Taro lives in JOI City, which is divided into a grid by $a$ roads running straight in the north–south direction and $b$ roads running straight in the east–west direction.

The $a$ north–south roads are numbered $1, 2, \dots, a$ from west to east. The $b$ east–west roads are numbered $1, 2, \dots, b$ from south to north. The intersection where the $i$-th north–south road (from the west) meets the $j$-th east–west road (from the south) is denoted $(i, j)$.

Taro lives near intersection $(1, 1)$ and commutes by bicycle to JOI High School, which is near intersection $(a, b)$. The bicycle can move only along the roads. To shorten his commute, Taro always moves only toward the east or the north.

Currently, construction is underway at $n$ intersections $(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)$, and Taro cannot pass through an intersection that is under construction.

How many ways can Taro commute from intersection $(1, 1)$ to intersection $(a, b)$, moving only east or north while avoiding every intersection under construction? Write a program that computes the number of commute routes $m$.

The first line contains two integers $a$ and $b$, separated by a space, giving the number of north–south roads and the number of east–west roads, respectively. They satisfy $1 \le a, b \le 16$.

The second line contains an integer $n$, the number of intersections under construction, satisfying $1 \le n \le 40$.

Each of the following $n$ lines gives the position of an intersection under construction: the $i$-th such line contains two space-separated integers $x_i$ and $y_i$, indicating that intersection $(x_i, y_i)$ is under construction. They satisfy $1 \le x_i, y_i \le 16$.

Print a single line containing only $m$, the number of Taro's commute routes.

The figure below shows the case $a = 5$, $b = 4$, $n = 3$, where the intersections under construction are $(2, 2)$, $(2, 3)$, and $(4, 2)$.

In this case there are $m = 5$ commute routes. All five routes are illustrated below.