记录编号	56264	评测结果	AAAAAAAAAA
题目名称	[HAOI 2012]容易题	最终得分	100
用户昵称	DavidMason	是否通过	通过
代码语言	Pascal	运行时间	0.179 s
提交时间	2013-03-27 21:31:15	内存使用	23.05 MiB

const p=1000000007;

var
          n,m,k:longint; q:int64;
          f,x,y:array[0..1000010] of int64;

procedure init;
begin
          assign(input,'easy.in'); reset(input);
          assign(output,'easy.out'); rewrite(output);
end;

procedure terminate;
begin
          close(input); close(output); halt;
end;

procedure qsort(l,r:longint);
var
          i,j:longint; t,mid1,mid2:int64;
begin
          i:=l; j:=r; mid1:=x[(l+r) shr 1]; mid2:=y[(l+r) shr 1];
          repeat
                while (x[i]<mid1) or ((x[i]=mid1) and (y[i]<mid2)) do inc(i);
                while (x[j]>mid1) or ((x[j]=mid1) and (y[j]>mid2)) do dec(j);
                if i<=j then begin
                   t:=x[i]; x[i]:=x[j]; x[j]:=t; t:=y[i]; y[i]:=y[j]; y[j]:=t; inc(i); dec(j);
                end;
          until i>j; if i<r then qsort(i,r); if l<j then qsort(l,j);
end;

function minus(a,b:int64):int64;
begin
          a:=a-b; while a>=p do dec(a,p); while a<0 do a:=a+p; a:=a mod p; exit(a);
end;

function plus(a,b:int64):int64;
begin
          a:=a+b; while a>=p do dec(a,p); while a<0 do a:=a+p; a:=a mod p; exit(a);
end;

function power(a,b,p:int64):int64;
var
          x:int64;
begin
          x:=1;
          while b<>0 do begin
                if b and 1=1 then x:=((x mod p)*(a mod p)) mod p;
                b:=b shr 1; a:=((a mod p)*(a mod p)) mod p;
          end; exit(x);
end;

procedure main;
var
          i:longint; count,tmp,last,last1:int64; ans:int64;
begin
          read(n,m,k); for i:=1 to k do read(x[i],y[i]); qsort(1,k);
          q:=((int64(int64(n+1)*int64(n))) div 2) mod p; last:=0; last1:=0; count:=0; tmp:=0;
          for i:=1 to k do begin
              if x[i]<>last then begin
                 {if i=k+1 then begin
                    ans:=1;
                 end;}
                 if count<>0 then f[count]:=minus(f[count],tmp);
                 tmp:=y[i]; inc(count); f[count]:=q; last:=x[i]; last1:=y[i];
              end else begin
                 if y[i]<>last1 then begin tmp:=plus(tmp,y[i]); last1:=y[i]; end;
              end;
          end; f[count]:=minus(f[count],tmp); ans:=1; ans:=(ans*(power(q,m-count,p))) mod p;
          for i:=1 to count do ans:=(ans*f[i]) mod p; writeln(ans);
end;

begin
        init;
        main;
        terminate;
end.