Mouse Journey

Interview

Time limit2sMemory limit512 MB

Summary

Count monotone right/down paths on an R by C grid from (1,1) to (R,C) that avoid K blocked cat cells.

Level: Easy3 of 10
Topics: Dynamic programming, Matrix, Combinatorics
Solved: No attempts yet

Problem

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.

Input

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

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.

Examples2

Example 1
Input
```
2 3
1
2 1
```
Expected output
```
2
```
Example 2
Input
```
3 4
3
2 3
2 1
1 4
```
Expected output
```
1
```