记录编号	391567	评测结果	AAAAAAAAAA
题目名称	[HAOI 2012]容易题	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.047 s
提交时间	2017-04-06 13:15:40	内存使用	1.68 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <list>
#include <queue>
#include <vector>
#include <deque>
#include <cctype>
using namespace std;
namespace IO{
  char buf[1<<18], *fs, *ft;
  inline char getc(){
    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin)),fs==ft)?0:*fs++;
  }
  template<typename T>
  void splay(T &r){
    char c; bool s = false;
    while((c = getc())){
      if(c >= '0' && c <= '9'){
        r = c^0x30; break;
      }else if(c == '-')s = true;
    }while(isdigit(c = getc()))
      r = ((r+(r<<2))<<1)+(c^0x30);
    if(s)r = -r;
  }
}using IO::splay;
typedef long long LL;
const LL MOD = 1000000007;
LL pow_mod(LL a, LL x, LL p){
  LL ans = 1;
  for(a %= p; x; x >>= 1, a = a*a%p)if(x&1)ans = ans*a%p;
  return ans;
}
int n, m, k;
struct info{
  int pos, val;
  bool operator<(const info &f)const{
    return pos < f.pos || (pos == f.pos && val < f.val);
  }
  bool operator==(const info &f)const{
    return pos == f.pos && val == f.val;
  }
}data[100003];
void solve1(){
  sort(data, data+k);
  int lim = unique(data, data+k)-data;
  LL ans = 1;
  LL inv2 = pow_mod(2, MOD-2, MOD);
  int p = 0;
  for(int i = 1; i <= m; i++){
    LL sum = (1ll*n*(n+1)%MOD)*inv2%MOD;
    while(p < lim && data[p].pos < i)p++;
    for(int j = p; j < lim && data[j].pos == i; j++)sum -= data[j].val;
    sum = (sum%MOD+MOD)%MOD;
    ans = ans*sum%MOD;
  }
  printf("%lld\n", ans);
}
int pro[100003];
void solve2(){
  sort(data, data+k);
  int p = 0;
  for(int i = 0; i < k; i++){
    if(!i || data[i].pos != data[i-1].pos)
      pro[++p] = data[i].val%MOD;
    else if(data[i].val != data[i-1].val)
      pro[p] = (pro[p]+data[i].val)%MOD;
  }
  LL ans = 1;
  LL inv2 = pow_mod(2, MOD-2, MOD);
  LL eval = (1ll*n*(n+1)%MOD)*inv2%MOD;
  for(int i = 1; i <= p; i++)ans = ans*((eval-pro[i]+MOD)%MOD)%MOD;
  printf("%lld\n", ans*pow_mod(eval, m-p, MOD)%MOD);
}
int main(){
 // freopen("test_data.txt", "r", stdin);
  freopen("easy.in", "r", stdin);
  freopen("easy.out", "w", stdout);
  splay(n); splay(m); splay(k);
  for(int i = 0; i < k; i++){
    splay(data[i].pos); splay(data[i].val);
  }
  if(m <= 1000)
    solve1();
  else solve2();
  return 0;
}