首先我们知道，对于所有种情况，我们可以将每一位可以放的
数的值加起来，所有位置的乘起来，等于的就是最后的答案，具体
为什么正确，可以根据乘法分配律来想一想。
那么对于所有不做要求的，快速幂直接算就行了，然后快排下，就知道
每个位置不放那些值，减掉后乘进去就行了。
/**************************************************************Problem: 2751User: BLADEVILLanguage: PascalResult: AcceptedTime:344 msMemory:1008 kb ****************************************************************///By BLADEVIL constd39 =1000000007;varn, m, k :longint;a, b :array[0..100010] of longint;ans :int64;procedure swap(var a,b:longint); varc :longint; beginc:=a; a:=b; b:=c; end;procedure qs(low,high:longint); vari, j, xx, yy :longint; begini:=low; j:=high; xx:=a[(i+j) div 2]; yy:=b[(i+j) div 2];while i<j dobeginwhile (a[i]<xx) or (a[i]=xx) and (b[i]<yy) do inc(i);while (a[j]>xx) or (a[j]=xx) and (b[j]>yy) do dec(j);if i<=j thenbeginswap(a[i],a[j]);swap(b[i],b[j]);inc(i); dec(j);end;end;if i<high then qs(i,high);if j>low then qs(low,j); end;procedure init; vari :longint; beginread(n,m,k);for i:=1 to k do read(a[i],b[i]);qs(1,k); end;function mi(a,b:int64):int64; varsum :int64; beginsum:=a;mi:=1;while b<>0 dobeginif b mod 2=1 then mi:=mi*sum mod d39;sum:=sum*sum mod d39;b:=b div 2;end; end;procedure main; vari :longint;sum, x, y, z :int64; beginsum:=m;x:=-1;for i:=1 to k dobeginif a[i]<>x thenbegindec(sum);x:=a[i];end;end;x:=n; y:=n+1;if x mod 2=0 then x:=x div 2 else y:=y div 2;x:=x mod d39;y:=y mod d39;x:=x*y mod d39;ans:=mi(x,sum);for i:=1 to k do if (a[i]=a[i-1]) and (b[i]=b[i-1]) then b[i-1]:=0;y:=-1;z:=-1;for i:=1 to k dobeginif a[i]<>y thenbeginif i<>1 then ans:=ans*z mod d39;z:=x;y:=a[i];z:=((x-b[i]) mod d39+d39) mod d39;end else z:=((z-b[i])mod d39+d39) mod d39;end;if z<>-1 then ans:=ans*z mod d39;writeln(ans); end;begininit;main; end.