考虑 $70\%$ 的做法，在已知前 $i-1$ 个数的所有乘积之和 $sum$ 的情况下，假设当前数可以取 $a_1,a_2,a_3,\dots$，则前 $i$ 个数的所有乘积之和为 $sum*\sum{a}$。显然后者为 $\frac{m(m+1)}{2}-\text{所有不能选的数之和}$，预处理后递推一下就可以。

扩展到 $100\%$ 的情况，好像没什么变化，就就加一个快速幂......

但要注意，这题要考虑取模的地方特别多，建议所有变量用之前都取个模。

代码：

#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
struct no{
	long long x,y;
	bool operator <(const no &ano)const{
		if(x==ano.x)return y<ano.y;
		return x<ano.x;
	}
};
no cannot[100010];
long long power(long long a,long long b){
	long long ji=1;
	a%=mod;
	while(b){
		if(b&1)ji=ji*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ji;
}
int main(){
	long long n,m,k;
	cin>>m>>n>>k;
	for(int i=1;i<=k;i++){
		cin>>cannot[i].x>>cannot[i].y;
	}
	sort(cannot+1,cannot+k+1);
	long long ji=0,h=cannot[1].y;
	for(int i=1;i<=k;i++){
		if(cannot[i].x==cannot[i+1].x){
			h+=cannot[i+1].y*(cannot[i].y!=cannot[i+1].y);
		}
		else{
			cannot[++ji]={cannot[i].x,h};
			h=cannot[i+1].y;
		}
	}
	long long ans=power(m*(m+1)/2,n-ji);
	for(int i=1;i<=ji;i++){
		ans=ans*((m*(m+1)/2-cannot[i].y)%mod)%mod;
	}
	cout<<ans;
	return 0;
}

qkw:

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>
const int P=1e9+7,N=1e5+10;
int a[N],len;
PII q[N];
set<PII>s;
int qpow(int a,int b){int ans=1%P;for(;b;b>>=1,a=a*a%P)if(b&1)ans=ans*a%P;return ans;}
signed main()
{
    int n,m,k;scanf("%lld%lld%lld",&n,&m,&k);
    int sum=(n*(n+1)/2+P)%P;
    for(int i=1;i<=k;i++)
    {
        int x,y;scanf("%lld%lld",&x,&y);
        q[i].first=x,q[i].second=y;
    }
    sort(q+1,q+k+1);
    for(int i=1;i<=k;i++)
    {
        if(q[i].first!=q[i-1].first)a[++len]=q[i].second,a[len]%=P;
        else if(q[i].second!=q[i-1].second)a[len]+=q[i].second,a[len]%=P;
    }
    int mlen=m-len;
    int ans=qpow(sum,mlen);
    for(int i=1;i<=len;i++)ans=((ans*(sum-a[i]))%P+P)%P;
//  for(int i=1;i<=len;i++)ans=ans*(sum-a[i])%P;
    printf("%lld\n",ans);
    return 0;
}