容易题，题解

题目链接

分析：

　　题意很明白，也很显然，这一题要推式子，那么我们就直接想一下可以推出什么来，首先我们假设第i位可取的数字有di个分别为ai1，ai2，。。。ai(di)。于是我们有，

S（要求的和）=a11*a21*a31*...*an1+a11*a21*a31*...*an2+a11*a21*a31*...*an3+...+a11*a21*a31*...*an(dn)+...+a1(d1)*a2(d2)*a3(d3)*...*an(dn).

然后多提取几次公因式就是(a11+a12+...+a1d1)*(a21+a22+...+a2d2)*...*(an1+an2+...+andn).

然后就好办了因为ai是1——n的数字，所以最初的和是可以确定的，然后出现一个需要限制的就减一点，最后没限制的那个用快速幂，再乘上有限制的。记得有需要去重的去重。

　　最后是代码：

#include <cstdio>
#include <map>
using namespace std;
const int mod=1e9+7;
const int maxn=1e5+10;
map<int,int> ma;
map<pair<int,int>,bool> ma2;
int s[maxn];
int js;
int pow(long long a,int p){
    a%=(long long)mod;
    int s=a;
    int ans=1;
    while(p){
        if(p&1)
            ans=(long long)ans*(long long)s%(long long)mod;
        p>>=1;
        s=(long long)s*(long long)s%(long long)mod;
    }
    return ans;
}
int main(){
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    int js1,js2;
    for(int i=1;i<=k;i++){
        scanf("%d%d",&js1,&js2);
        if(ma2[make_pair(js1,js2)])
            continue;
        ma2[make_pair(js1,js2)]=1;
        if(!ma[js1]){
            js++;
            ma[js1]=js;
            s[ma[js1]]=(long long)n*(long long)(n+1)/2ll%(long long)mod;
        }
        s[ma[js1]]=(s[ma[js1]]-js2+mod)%mod;
    }
    int ans=pow((long long)n*(long long)(n+1)/2ll,m-js);
    for(int i=1;i<=js;i++)
        ans=(long long)ans*(long long)s[i]%(long long)mod;
    printf("%d",ans);
    return 0;
}