第一行为用空格隔开的两个正整数 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可能稍大于原设定)
BZPRO在C 部落，双十字是非常重要的一个部落标志。所谓双十字，如下面两个例子，由两条水平的和一条竖直的“1”线段组成，要求满足以下几个限制：
.jpg)
我们可以找到 5 个满足条件的双十字，分别如下：
注意最终的结果可能很大，只要求输出双十字的个数 mod 1,000,000,009 的值
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