题解：hzw大神的博客说的很清楚嘛
朴素的做法就是每个点如果它不是墓地那么就可形成十字架的数量就是这个c（点左边的树的数量，k）*c（点右边的树的数量，k）*c（点上边的树的数量，k）*c（点下边的树的数量，k）。这样的话要枚举每个点，复杂度很明显爆表。
再仔细分析一下，其实完全可以不用枚举每个点，只需要枚举那些树的位置就可以，（下面的点指的都是树而非点？？蒟蒻语言不好）在同一列的两棵相邻的树之间的点的c（点左边的树的数量，k）*c（点右边的树的数量，k）是一样的，但是还是需要Σc（点上边的树的数量，k）*c（点下边的树的数量，k）（乘法分配率，自己yy一下），朴素枚举这些还是要复杂度爆表，于是问题就是如果在logn时间内搞定这个东西，于是想到如果维护“Σc（点上边的树的数量，k）*c（点下边的树的数量，k）”的信息（询问区间和，想到树状数组或者线段树），（有点类似于那个悬梁法）就是这个点的上一个点和这个点之间的“c（点上边的树的数量，k）*c（点下边的树的数量，k）”是有一点联系的，yy一下就是这个点在下一行中是作为下面的点上面的树的数量……于是修改量就是c（原来上边的树的数量+1，k）*c（原来下边的树（其实包括了这个点也就是这棵树）的数量-1，k）- c（原来上边的树的数量，k）*c（原来下边的树（其实包括了这个点也就是这棵树）的数量，k）。
然后只需要在一开始离散化一下树，再给树排个序，就差不多了，还用到了前缀和小小的搞一下。
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 type arr=record x,y:longint; end; const mm=2147483648; var i,j,kk,l,n,m,w,now,tot:longint; a:array[0..100500]of arr; bit:array[0..400000]of int64; b,d,totx,toty,hash:array[0..400000]of longint; c:array[0..100500,0..11]of int64; ans,ans1,ans2,ans3:int64; procedure swap(var x,y:longint); var i:longint; begin i:=x; x:=y; y:=i end; function min(x,y:longint):longint; begin if x>y then exit(y); exit(x) end; function lowbit(x:longint):longint; begin exit(x and (-x)) end; function find(x:longint):longint; var l,r,mid:longint; begin l:=1;r:=tot; while l<=r do begin mid:=(l+r) >> 1; if hash[mid]<x then l:=mid+1 else if hash[mid]>x then r:=mid-1 else exit(mid); end end; procedure work; var i,j:longint; begin c[0][0]:=1; for i:=1 to w do begin c[i,0]:=1; for j:=1 to min(kk,i) do c[i,j]:=(c[i-1,j]+c[i-1,j-1]) mod mm; end end; procedure qsort1(l,r:longint); var i,j,k,mid:longint; begin i:=l; j:=r; mid:=b[(l+r) >>1]; repeat while b[i]<mid do inc(i); while b[j]>mid do dec(j); if i<=j then begin swap(b[i],b[j]); inc(i); dec(j); end; until i>j; if l<j then qsort1(l,j); if i<r then qsort1(i,r) end; procedure qsort2(l,r:longint); var i,j,k,mid1,mid2:longint; begin i:=l; j:=r; mid1:=a[(l+r) >>1].y; mid2:=a[(l+r) >>1].x; repeat while (a[i].y<mid1) or (a[i].y=mid1) and (a[i].x<mid2) do inc(i); while (a[j].y>mid1) or (a[j].y=mid1) and (a[j].x>mid2) do dec(j); if i<=j then begin swap(a[i].x,a[j].x); swap(a[i].y,a[j].y); inc(i); dec(j); end; until i>j; if l<j then qsort2(l,j); if i<r then qsort2(i,r) end; procedure add(x:longint;y:int64); begin while x<=tot do begin bit[x]:=(bit[x]+y) mod mm; inc(x,lowbit(x)); end end; function ask(x:longint):int64; var sum:int64; begin sum:=0; while x>0 do begin sum:=(sum+bit[x]) mod mm; dec(x,lowbit(x)); end; exit(sum) end; begin readln(n,m); readln(w); fillchar(totx,sizeof(totx),0); fillchar(toty,sizeof(toty),0); fillchar(d,sizeof(d),0); fillchar(bit,sizeof(bit),0); fillchar(c,sizeof(c),0); fillchar(hash,sizeof(hash),0); for i:=1 to w do begin read(a[i].x,a[i].y); b[2*i-1]:=a[i].x; b[2*i]:=a[i].y; end; qsort1(1,2*w); hash[1]:=b[1]; tot:=1; for i:=2 to 2*w do if b[i]<>b[i-1] then begin inc(tot); hash[tot]:=b[i]; end; read(kk); work; for i:=1 to w do begin inc(totx[find(a[i].y)]); inc(toty[find(a[i].x)]); end; qsort2(1,w); now:=0; ans:=0; for i:=1 to w do begin j:=find(a[i].x); if (i>1) and (a[i].y=a[i-1].y) then begin inc(now); ans1:=ask(j-1)-ask(find(a[i-1].x)) mod mm; ans2:=c[now,kk]*c[totx[find(a[i].y)]-now,kk] mod mm; ans:=(ans+ans1*ans2) mod mm; end else now:=0; inc(d[j]); ans3:=(c[d[j],kk]*c[toty[j]-d[j],kk]-c[d[j]-1,kk]*c[toty[j]-d[j]+1,kk])mod mm; if ans3<>0 then add(j,ans3); end; if ans<0 then ans:=ans+mm; writeln(ans); end.