Tom and Jerry

Jerry the Mouse has finally tired of being chased by Tom the Cat, and has decided to strike back. He has secretly constructed a catapult in the lower right cell of the rectangular grid representing the living room. It is now time to fire the catapult.1 However, Jerry’s current hiding place is located in the upper left cell of the room.

Jerry wants to move from his hiding place to the catapult, but since he is hungry he also wants to pick up a piece of cheese on the way. Due to Tom watching the room closely, Jerry does not want to walk an unecessarily long path – therefore, he will only take steps downwards and to the right in the grid.

To plan his trip to the catapult, he wants to know how many paths he can take, given the movement restriction and that he must fetch at least one cheese on the way.

\includegraphics[width=0.35\textwidth ]{grid}
Figure 1: The three possible paths in Sample Input 1


The first line of input contains two integers $1 \le w, h \le 50\, 000$, the width and height of the room. On the second line, there is an integer $0 \le n \le 8$, the number of cheeses in the room. Each of the following $n$ lines contains two integers $x$ and $y$ ($1 \le x \le w$, $1 \le y \le h$), the coordinates of a cheese. No two cheeses are at the same position, but there may be cheese on the start and end positions.


Output the number of paths Jerry can take, modulo the prime $1\, 000\, 000\, 007$.

Sample Input 1 Sample Output 1
3 3
1 2
Sample Input 2 Sample Output 2
5 5
4 3
3 4
Sample Input 3 Sample Output 3
4 5
2 3
4 5


  1. Please keep in mind that this is a fictional story. Kattis does not endorse catapulting cats in any way, shape, or form.