P3221 [HNOI2012] Double Cross

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$.

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 a single integer: the number of double crosses $\bmod\ 10^9+9$.

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