After watching Game of Thrones, Bruce decided to make a family symbol. He wants his symbol to be special, so he chooses the double cross as his symbol. The double cross is made by two horizontal and one vertical line segments, which are marked by 1 in a 01 grid. A valid double cross must satisfy the following constraints:

• The two horizontal line segments cannot be next to each other. There is at least one spare row between the two horizontal line segments.

• The top of the vertical segment must be higher than both of the horizontal segments, and the bottom of the vertical segment must be lower than both of the horizontal segments.

• The vertical segment must pass the middle points of the two horizontal segments.

• The top horizontal segment must be shorter than the bottom horizontal segment.

The following figure illustrates two valid double crosses. The right double cross in the figure is the minimal double cross.

..........
....1.....          ..1..
..11111...          .111.
....1.....          ..1..
111111111.          11111
....1.....          ..1..
....1.....

Given an ~R \times C~ grid marked with 0 and 1, please write a program to find the number of valid double crosses in the grid.

Input Specification

The first line of input will consist of two integers, ~R~ and ~C~ (~1 \le R, C \le 10\,000~ and ~R \times C \le 1\,200\,000~), the number of rows and the number of columns in the grid, respectively.

The second line of input will consist of one integer, ~N~ (~0 \le N \le 10\,000~), which is the number of 0s in the grid.

Each of the next ~N~ lines will consist of two integers separated by a space, ~r~ and ~c~ (~1 \le r \le R~, ~1 \le c \le C~), which represents that there is a 0 at ~(r, c)~ in the grid.

Output Specification

Output one integer, the number of double crosses in the grid modulo ~1\,000\,000\,009~ ~(= 10^9+9)~.

Sample Input

6 8
12
1 2
1 3
1 4
1 6
2 2
3 2
3 3
3 4
3 7
6 4
6 6
4 8

Sample Output

5

Explanation of Output for Sample Input

The size of the input grid is ~R=6~, ~C=8~. The grid and all the valid double crosses are illustrated in the following figure. There are 5 valid double crosses in total.

10001011    ....1...    ....1...    ....1...    ....1...    ....1...
10111111    ...111..    ...111..    ...111..    ...111..    ..11111.
10001101    ....1...    ....1...    ....1...    ....1...    ....1...
11111110    ..11111.    ..11111.    ....1...    ....1...    ....1...
11111111    ....1...    ....1...    ..11111.    .1111111    .1111111
11101011    ........    ....1...    ....1...    ....1...    ....1...