双十字 ### 题目描述 在 C 部落，双十字是非常重要的一个部落标志。所谓双十字，如下面两个例子，由两条水平的和一条竖直的 `1` 线段组成： ``` .......... ....1..... ..1.. ..11111... .111. ....1..... ..1.. .1111111.. 11111 ....1..... ..1.. ....1..... .......... ``` 合法的双十字要求满足以下几个限制： - 两条水平的线段不能在相邻的两行。 - 竖直线段上端必须严格高于两条水平线段，下端必须严格低于两条水平线段。 - 竖直线段必须将两条水平线段严格划分成相等的两半。 - 上方的水平线段必须严格短于下方的水平线段。 所以上面右边的例子是满足要求的最小的双十字。 现在给定一个 $R\times C$ 的 `01` 矩阵，要求计算出这个 `01` 矩阵中有多少个双十字。例如下面这个例子，`01` 矩阵如下： ```txt 10001011 10111111 10001101 11111110 11111111 11101011 ``` 我们可以找到 $5$ 个满足条件的双十字，分别如下： ```txt ....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` 的坐标两两不同。 其中，保证 $5\le R,C\le 10^4$，$0\le N\le 10^4$，$RC\le 2\times 10^6$。 ### 输出描述 输出一行一个整数，为双十字的个数 $\bmod\ 10^9+9$ 的值。 ### 输入输出样例 #### 示例 1 >输入 ```txt 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 ``` >输出 ```txt 5 ```