想说的话
讲道理一点没觉得这题简单...
直接推的话显然处理不了。。。所以考虑每个答案的贡献。默认的的是一个数的贡献是(sum_{i=1}^{n})
然后我们考虑的就是针对没有限制的元素，发现这些元素的贡献值是一样的。对于这些元素 我们用一个快速幂取余得到结果，剩下的我们直接把限制元素减掉就是贡献。直接乘进去就好。
然后这题的样例很有良心（然鹅我一开始并没注意）
有相同的数据，换句话说我们需要去重。
按理说去重首先可以用Hash，但我并不会。然后去重函数又用不好（蒟蒻发言）
然后看到网上一个很友好的写法，用map
用bool来映射long long，避免内存过大还省时间（说白了就是菜）
开一个结构体limit来维护我们限制的元素和限制的值，然后就完了。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
#include <vector>
using namespace std;
const int maxn=100000+10,mod=1e9+7;
#define ll long long
map<ll,bool> jojo;//long long->bool去重
struct node{
ll num,dis;
bool operator <(const node b)const{
if(num==b.num) return dis<b.dis;
return num<b.num;
}
}lim[maxn];
ll n,m,k,ans=1;
ll sum,tot,cnt;
void Pow(ll &ans,ll a,ll b){//快速幂，两种随便那个都行，一开始以为写错了就多写了一个
ll q=a;
while(b){
if(b&1) ans=(ans*q)%mod;
q=(q*q)%mod;
b>>=1;
}
}
ll Poww(ll a,ll b){
if(!b) return 1;
ll tmp=Poww(a,b>>1);
tmp=(tmp*tmp)%mod;
if(b&1) tmp*=a;
return tmp%mod;
}
int main(){
scanf("%d %d %d",&n,&m,&k);
sum=(((n+1)*n)>>1)%mod;
for(int i=1;i<=k;i++){
scanf("%d %d",&lim[i].num,&lim[i].dis);
}
sort(lim+1,lim+1+k);//排一下序，方便去重
jojo.clear();
for(int i=1;i<=k;i++){
if(lim[i].num==lim[i+1].num){
if(!jojo[lim[i].dis]){
cnt+=lim[i].dis;
jojo[lim[i].dis]=1;
}
}
else{
tot++;
if(!jojo[lim[i].dis]) cnt+=lim[i].dis;
ans=(ans*((sum-cnt)%mod))%mod;
cnt=0;
jojo.clear();//记得每次对一个位置的数去完重后清空。
}
}
Pow(ans,sum,m-tot);
//ans=(ans*Poww(sum,m-tot))%mod;
printf("%lld
",(ans%mod+mod)%mod);//防止出现负数，一开始没加WA了，还以为是快速幂写错了...
return 0;
}