题意

• 长度为m的序列，每个位置可选1~n，有k条限制，限制位置a不能选择b
• 求解所有序列内部求积的和

思路

• 加法原理和乘法原理
• 如果没有限制，每个位置可以选择1~n，m个位置
• 每个位置的贡献为(n*(n+1)/2)总价值为(n*(n+1)/2)^m
• 然后对于没限制的部分就按照公式算
• 有限制的部分，就是在贡献中减去限制的值

代码

#include<bits/stdc++.h>
using namespace std;

const int p=1e9+7;
long long qpow(long long a,long long b){
    a%=p;
    long long res=1;
    while(b){
        if(b&1) res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res;
}
long long ans=0;
set<int> st[101010];
map<int,int> mp;
int cnt;
int main(){
    long long n,m,k;
    cin >> n >> m >> k;
    for(int i=0;i<k;i++){
        int x,y;
        cin >> x >> y;
        if(mp.find(x)==mp.end()){
            mp[x]=cnt++;
        }
        st[mp[x]].insert(y);
    }
    ans=qpow(n*(n+1)%p/2,m-cnt);
    for(int i=0;i<cnt;i++){
        long long cur=n*(n+1)%p/2;
        for(auto j:st[i]){
            cur=(cur-j+p)%p;
        }
        ans=ans*cur%p;
    }
    cout << ans << endl;

    return 0;
}