Mouse Journey

You are a mouse living in a cage in a large laboratory. The laboratory consists of a rectangular grid of square cages with $R$ rows and $C$ columns in total ($1 \le R, C \le 25$).

For exercise, the laboratory owners let you move between cages. You may move only to the adjacent cage immediately to the right in the same row, or to the adjacent cage immediately below in the same column. You cannot move diagonally, left, or up.

Your cage sits in one corner of the laboratory, labeled $(1, 1)$ (top-most row, left-most column). You want to visit your brother, who lives in the cage labeled $(R, C)$ (bottom-most row, right-most column) in the diagonally opposite corner. However, some cages contain cats and cannot be passed through.

Your brother, who loves numbers, wants to know how many different paths there are from your cage to his that never pass through a cat cage. Write a program that computes the number of cat-free paths.

The first line contains two integers $R$ and $C$, separated by a single space, giving the number of rows and columns respectively. The second line contains the integer $K$, the number of cages that contain cats. Each of the next $K$ lines contains the row and column position (in that order) of a cage that contains a cat. None of the $K$ cat cages are repeated, and all of them are valid positions. Also, $(1, 1)$ and $(R, C)$ are never cat cages.

Output a single non-negative integer: the number of paths from your cage at $(1, 1)$ to your brother's cage at $(R, C)$. You may assume the answer is strictly less than 1,000,000,000.