传送门
组合数学一眼题。
感觉一直做这种题智商会降低。
利用组合数学的分步计数原理。
只用关心每个数不被限制的取值的总和然后乘起来就可以了。
对于大部分数都不会被限制，总和都是n(n+1)2\frac{n(n+1)}{2}2n(n+1).
这部分数的贡献直接用快速幂算。
剩下最多只有1e51e51e5个数。
直接暴力算出每个数不被限制的取值的总和。
代码：
#include<bits/stdc++.h>
#include<tr1/unordered_map>
using namespace std;
typedef long long ll;
const int mod=1e9+7,N=1e5+5;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
int n,m,k,tot=0,siz=0;
struct Node{
int pos,val;
friend inline bool operator<(const Node&a,const Node&b){return a.pos==b.pos?a.val<b.val:a.pos<b.pos;}
friend inline bool operator==(const Node&a,const Node&b){return a.pos==b.pos&&a.val==b.val;}
}p[N];
inline int ksm(int x,int p){int ret=1;for(;p;p>>=1,x=(ll)x*x%mod)if(p&1)ret=(ll)ret*x%mod;return ret;}
int main(){
n=read(),m=read(),k=read();
for(int i=1;i<=k;++i)p[i].pos=read(),p[i].val=read();
sort(p+1,p+k+1),k=unique(p+1,p+k+1)-p-1;
for(int i=1;i<=k;++i){
if(p[i].pos^p[siz].pos)p[++siz]=p[i];
else (p[siz].val+=p[i].val)%=mod;
}
int tmp=(ll)n*(n+1)/2%mod,ans=ksm(tmp,m-siz);
for(int i=1;i<=siz;++i)ans=(ll)(tmp-p[i].val+mod)%mod*ans%mod;
cout<<ans;
return 0;
}