[HNOI2012] 双十字

在 C 部落，双十字是非常重要的一个部落标志。所谓双十字，如下面两个例子，由两条水平的和一条竖直的 `1` 线段组成： ``` .......... ....1..... ..1.. ..11111... .111. ....1..... ..1.. .1111111.. 11111 ....1..... ..1.. ....1..... .......... ``` 合法的双十字要求满足以下几个限制： - 两条水平的线段不能在相邻的两行。 - 竖直线段上端必须严格高于两条水平线段，下端必须严格低于两条水平线段。 - 竖直线段必须将两条水平线段严格划分成相等的两半。 - 上方的水平线段必须严格短于下方的水平线段。 所以上面右边的例子是满足要求的最小的双十字。 现在给定一个 $R\times C$ 的 `01` 矩阵，要求计算出这个 `01` 矩阵中有多少个双十字。例如下面这个例子，`01` 矩阵如下： ``` 10001011 10111111 10001101 11111110 11111111 11101011 ``` 我们可以找到 $5$ 个满足条件的双十字，分别如下： ``` ....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... ``` 注意最终的结果可能很大，只要求输出双十字的个数 $\bmod\ 10^9+9$ 的值。

第一行为用空格隔开的两个正整数 $R$ 和 $C$，分别表示 `01` 矩阵的行数和列数。 第二行是一个非负整数 $N$，表示 `01` 矩阵中 `0` 的个数。 接下来的 $N$ 行，每行为用空格隔开的两个正整数 $x$ 和 $y$（$1\le x\le R,1\le y\le C$），表示 $(x,y)$ 是 `0`。数据保证 $N$ 个 `0` 的坐标两两不同。

一行一个整数，为双十字的个数 $\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

对于 $100\%$ 的数据，保证 $5\le R,C\le 10^4$，$0\le N\le 10^4$，$RC\le 2\times 10^6$。