题号：NC20095
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
在C 部落，双十字是非常重要的一个部落标志。所谓双十字，如下面两个例子，由两条水平的和一条竖直的“1”线段组成，要求满足以下几个限制：
我们可以找到 5 个满足条件的双十字，分别如下：
注意最终的结果可能很大，只要求输出双十字的个数 mod 1,000,000,009 的值·两条水平的线段不能在相邻的两行。·
竖直线段上端必须严格高于两条水平线段，下端必须严格低于两条水平线段。 ·竖直线段必须将两条水平线段严格划分成相等的两半。·
上方的水平线段必须严格短于下方的水平线段。 所以上面右边的例子是满足要求的最小的双十字。
现在给定一个 R*C的01 矩阵，要求计算出这个 01 矩阵中有多少个双十字。例如下面这个例子，R=6,C=8，01 矩阵如下：
输入描述:
第一行为用空格隔开的两个正整数 R和C，分别表示01矩阵的行数和列数。
输入文件第二行是一个非负整数N,表示01矩阵中”0“的个数。
接下来的N行，每行为用空格隔开的两个正整数x和y(1<=x<=R,1<=y<=C)，表示(x,y)是一个”0“。数据保证N个”0“的坐标两两不同。
数据保证R,C,N<=10,000,R*C<=1,000,000.(事实上R*C可能稍大于原设定)
输出描述:
D mod 1,000,000,009 的结果，其中D 为要求的 01矩阵中双十字的个数。
备注:
对于100%的数据，保证