4597: 老鼠的旅行
[Creator : ]
Description
You are a mouse that lives in a cage in a large laboratory.
你是一只生活在笼子里的实验室老鼠。
The laboratory is composed of one rectangular grid of square cages, with a total of $R$ rows and $C$ columns of cages ($1 ≤ R,C ≤ 25$).
实验室是一个 $R$ 行 $C$ 列的格子矩阵 $(1 ≤ R,C ≤ 25)$，每个格子是一个笼子。
To get your exercise, the laboratory owners allow you to move between cages.
为了让你锻炼身体，实验室管理员允许你在笼子之间移动。
You can move between cages either by moving right between two adjacent cages in the same row, or by moving down between two adjacent cages in the same column.
你只能向右和向下移动。
You cannot move diagonally, left or up.
你不能斜着移动，也不能向上和向左移动。
Your cage is in one corner of the laboratory, which has the label $(1,1)$ (to indicate top-most row, left-most column).
你所在的笼子是实验室的左上角，标记为 $(1,1)$
You would like to visit your brother who lives in the cage labelled $(R,C)$ (bottom-most row, right-most column), which is in the other corner diagonally.
你想去右下角的笼子 $(R,C)$ 里找你的女朋友。
However, there are some cages which you cannot pass through, since they contain cats.
但是有一些笼子是不能经过的，因为里面有猫。
Your brother, who loves numbers, would like to know how many different paths there are between your cage and his that do not pass through any cat cage. Write a program to compute this number of cat-free paths.
你女朋友很爱数学，她想要知道有多少条不同的路径可以从你的笼子到达她的笼子。写一个程序来计算吧。
你是一只生活在笼子里的实验室老鼠。
The laboratory is composed of one rectangular grid of square cages, with a total of $R$ rows and $C$ columns of cages ($1 ≤ R,C ≤ 25$).
实验室是一个 $R$ 行 $C$ 列的格子矩阵 $(1 ≤ R,C ≤ 25)$，每个格子是一个笼子。
To get your exercise, the laboratory owners allow you to move between cages.
为了让你锻炼身体，实验室管理员允许你在笼子之间移动。
You can move between cages either by moving right between two adjacent cages in the same row, or by moving down between two adjacent cages in the same column.
你只能向右和向下移动。
You cannot move diagonally, left or up.
你不能斜着移动，也不能向上和向左移动。
Your cage is in one corner of the laboratory, which has the label $(1,1)$ (to indicate top-most row, left-most column).
你所在的笼子是实验室的左上角，标记为 $(1,1)$
You would like to visit your brother who lives in the cage labelled $(R,C)$ (bottom-most row, right-most column), which is in the other corner diagonally.
你想去右下角的笼子 $(R,C)$ 里找你的女朋友。
However, there are some cages which you cannot pass through, since they contain cats.
但是有一些笼子是不能经过的，因为里面有猫。
Your brother, who loves numbers, would like to know how many different paths there are between your cage and his that do not pass through any cat cage. Write a program to compute this number of cat-free paths.
你女朋友很爱数学，她想要知道有多少条不同的路径可以从你的笼子到达她的笼子。写一个程序来计算吧。
Input
The first line of input contains two integers $R$ and $C$,
separated by one space representing the number of rows and columns
(respectively).
On the second line of input is the integer $K$, the number of cages that contain cats.
The next $K$ lines each contain the row and column positions (in that order) for a cage that contains a cat. None of the K cat cages are repeated, and all cages are valid positions. Note also that $(1,1)$ and $(R,C)$ will not be cat cages.
第一行包含两个整数 $R$ 和 $C$。
第二行一个整数 $K$，代表包含猫的笼子的个数。
接下来 $K$ 行包含 $K$ 个不同的位置信息，代表 $K$ 个包含猫的笼子的位置信息，注意 $(1,1)$ 和 $(R,C)$ 这两个位置是不会有猫的。
On the second line of input is the integer $K$, the number of cages that contain cats.
The next $K$ lines each contain the row and column positions (in that order) for a cage that contains a cat. None of the K cat cages are repeated, and all cages are valid positions. Note also that $(1,1)$ and $(R,C)$ will not be cat cages.
第一行包含两个整数 $R$ 和 $C$。
第二行一个整数 $K$，代表包含猫的笼子的个数。
接下来 $K$ 行包含 $K$ 个不同的位置信息，代表 $K$ 个包含猫的笼子的位置信息，注意 $(1,1)$ 和 $(R,C)$ 这两个位置是不会有猫的。
Output
Output the non-negative integer value representing the
number of paths between your cage at position $(1,1)$ and your brother’s
cage at position $(R,C)$. You can assume the output will be strictly less
than $1,000,000,000$.
输出一个非负整数代表你可以去你女朋友笼子里的路径数目，你可以假设这个输出会严格小于 $1,000,000,000$。
输出一个非负整数代表你可以去你女朋友笼子里的路径数目，你可以假设这个输出会严格小于 $1,000,000,000$。
Sample 1 Input
2 3
1
2 1
Sample 1 Output
2