记录编号	56549	评测结果	AAAAAAAAAA
题目名称	[HAOI 2012]容易题	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.174 s
提交时间	2013-03-31 16:33:55	内存使用	5.44 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const long long MOD=1000000007;//模这个数
//若干个(1~n)乘起来,若干个有限制的
long long n,m,k;
//n是取值范围,m是数列元素个数,k是限制条数
long long nsum;//1~n求和
long long lsum;//有限制的元素个数
class PAIR{
public:
	long long x,y;
};//表示一条限制:A[x]不等于y
bool cmp(PAIR a,PAIR b){
	if(a.x!=b.x) return a.x<b.x;
	return a.y<b.y;
}
PAIR s[100001];//最初读的限制
long long limit[100001]={0};//最终科学的限制
//这里面存放的每一项都代表扣剩下的值
void read(void){
	scanf("%lld%lld%lld",&n,&m,&k);
	long long i;
	for(i=0;i<k;i++){
		scanf("%lld%lld",&s[i].x,&s[i].y);
	}
}
void getsum(void){//尼玛求个1~n都这么麻烦
	long long temp;
	if(n&1){//奇数
		temp=n;
		temp*=(n+1)/2;
		nsum=temp;
	}
	else{
		temp=(n+1);
		temp*=(n/2);
		nsum=temp;
	}
}
bool getlim(void){
	//对原始的限制进行整理
	if(k==0){
		lsum=0;
		return 1;
	}
	sort(s,s+k,cmp);
	int i;
	lsum=0;
	limit[lsum]=s[0].y;
	for(i=1;i<k;i++){
		if(s[i].x==s[i-1].x&&s[i].y==s[i-1].y) continue;
		if(s[i].x!=s[i-1].x) lsum++;//对不同元素的限制
		limit[lsum]+=s[i].y;
		if(limit[lsum]>nsum) return 0;
	}
	lsum++;
	//最终的lsum就是个数
	for(i=0;i<lsum;i++) limit[i]=nsum-limit[i];
	return 1;
}
long long quickpow(long long x,long long y){//x^y%MOD
	long long ans=1;
	long long temp=x;
	while(y){
		if(y&1) ans=ans*temp%MOD;//奇数
		temp=temp*temp%MOD;
		y>>=1;
	}
	return ans;
}
long long calc_limit(void){
	long long ans=1;
	int i;
	for(i=0;i<lsum;i++){
		ans*=limit[i]%MOD;
		ans%=MOD;
	}
	return ans;
}
int main(){
	freopen("easy.in","r",stdin);
	freopen("easy.out","w",stdout);
	read();
	getsum();
	bool flag=getlim();
	if(!flag){
		printf("0\n");
		return 0;
	}
	long long ans1=calc_limit();
	long long ans2=quickpow(nsum%MOD,m-lsum);
	long long ans=ans1*ans2%MOD;
	printf("%lld\n",ans);
	return 0;
}