记录编号	393832	评测结果	AAAAAAAAAA
题目名称	[HAOI 2012]容易题	最终得分	100
用户昵称	JustWB	是否通过	通过
代码语言	C++	运行时间	0.091 s
提交时间	2017-04-12 09:57:29	内存使用	1.84 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 1000000007
using namespace std;
long long n,m,k,pk,all=1;
long long ans=1;
long long dq,lin;
bool p;
struct ppan
{
	long long x,y;
	ppan(){x=0;y=0;}
	bool operator < (const ppan A)const
	{
		if(x==A.x)return y<A.y;
		return x<A.x;
	}
}pan[100001];
long long pow(int mi)
{
	long long an=1;
	while(mi)
	{
		if(mi&1)
		{
			an=an*all%maxn;
		}
		all=all*all%maxn;
		mi>>=1;
	}
	return an;
}
int main()
{
	freopen("easy.in","r",stdin);
	freopen("easy.out","w",stdout);
	scanf("%lld%lld%lld",&n,&m,&k);
	all=(n+1)*n/2%maxn;
	if(k==0)
	{
		ans=pow(m)%maxn;
		printf("%lld",ans);
		return 0;
	}
	for(int i=1;i<=k;i++)
	{
		long long x,y;
		scanf("%lld%lld",&x,&y);
		pan[i].x=x;pan[i].y=y;
	}
	sort(pan+1,pan+k+1);
	dq=pan[1].x;lin=(all-pan[1].y)%maxn;
	if(lin<0)lin+=maxn;
	for(int i=2;i<=k;i++)
	{
		if(pan[i].x!=dq)
		{
			pk++;
			dq=pan[i].x;
			ans=ans*lin%maxn;
			lin=all-pan[i].y;
			if(lin<0)lin+=maxn;
			continue;
		}
		if(pan[i].y!=pan[i-1].y)
		{
			lin-=pan[i].y;
			if(lin<0)lin+=maxn;
		}
	}
	if(lin<0)lin+=maxn;
	pk++;ans=ans*lin%maxn;
	ans=ans*pow(m-pk)%maxn;
	printf("%lld",ans);
	return 0;
}