Description

In the C tribe, the double cross is a very important tribal emblem. A double cross, as in the two examples below, consists of two horizontal segments of 1 and one vertical segment of 1:

..........
....1.....      ..1..
..11111...      .111.
....1.....      ..1..
.1111111..      11111
....1.....      ..1..
....1.....
..........

A valid double cross must satisfy the following constraints:

• The two horizontal segments cannot be in two adjacent rows.
• The top end of the vertical segment must be strictly above both horizontal segments, and the bottom end must be strictly below both horizontal segments.
• The vertical segment must split each horizontal segment into two equal halves.
• The upper horizontal segment must be strictly shorter than the lower horizontal segment.

So the example on the right above is the smallest valid double cross.

Now given an $R \times C$ 01 matrix, compute how many double crosses are in this 01 matrix. For example, consider the following 01 matrix:

10001011
10111111
10001101
11111110
11111111
11101011

We can find $5$ valid double crosses, shown as follows:

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

....1...  ....1...
...111..  ..11111.
....1...  ....1...
....1...  ....1...
.1111111  .1111111
....1...  ....1...

Note that the final result can be large; output the number of double crosses $\bmod\ 10^9+9$.

Input Format

The first line contains two positive integers $R$ and $C$, separated by a space, denoting the numbers of rows and columns of the 01 matrix.

The second line contains a non-negative integer $N$, denoting the number of 0 in the 01 matrix.

Each of the next $N$ lines contains two positive integers $x$ and $y$ ($1 \le x \le R, 1 \le y \le C$), indicating that $(x, y)$ is 0. It is guaranteed that the coordinates of the $N$ zeros are pairwise distinct.

Output Format

Output a single integer: the number of double crosses $\bmod\ 10^9+9$.

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

5

Hint

For $100\%$ of the testdata, it is guaranteed that $5 \le R, C \le 10^4$, $0 \le N \le 10^4$, and $RC \le 2 \times 10^6$.

Translated by ChatGPT 5