请用快速幂解决：小Q特意出个自认为非常容易的题来满足大家，这道简单题是描述如下：

为了使得大家高兴，小Q特意出个自认为非常容易的题来满足大家，这道简单题是描述如下：
有一个数列AA已知对于所有的A[i]A[i]都是11~nn的自然数，并且知道对于一些A[i]A[i]不能取哪些值，要求你求出所有可能的数列有多少个，输出方案数mod 1000000007mod1000000007的值，怎么样，是不是很简单呢？呵呵！

你可以参考如下链接：
[haoi2012]容易题（数论+容斥的思想） - 列車員lcy - 博客园 描述 Description 为了使得大家高兴，小Q特意出个自认为的简单题（easy）来满足大家，这道简单题是描述如下： 有一个数列A已知对于所有的A[i]都是1~n的自然数，并且知道对于一些A[i] https://www.cnblogs.com/lcyhaha/p/7590189.html
如果对你有帮助，可以给我个采纳吗，谢谢!! 点击我这个回答右上方的【采纳】按钮

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<string>
#define K 1000000007 
#define ll long long
using namespace std;
inline ll read()
{
    char ch=getchar();
    ll x=0,f=1;
    while(ch>'9'||ch<'0')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
ll n,m,k;
ll M;
struct shadow
{
    ll x,y;
}a[101000],c[101000],b[106000];
ll d[101000];
bool mycmp(shadow x,shadow y)
{return x.x==y.x?x.y<y.y:x.x<y.x;}
ll work(ll p)
{
    ll ans=1;
    ll temp=p,s=M;
    while(temp!=0)
    {
        if(temp%2==1)
        {
            ans*=s;
            ans=(ans%K+K)%K;
        }
        ans%=K;
        temp/=2;
        s=(s*s%K+K)%K;
    }
    return ans;
}
int main()
{
    memset(c,0,sizeof(c));
    n=read();m=read();k=read();
    M=(1+n)*n/2%K;
    for(ll i=1;i<=k;i++)
    {
        a[i].x=read();
        a[i].y=read();
        c[i].x=a[i].x;
        c[i].y=a[i].y;
    }
    sort(a+1,a+1+k,mycmp);
    sort(c+1,c+1+k,mycmp);
    ll l=0;
    for(ll i=1;i<=k;i++)
    {
        if(c[i].x==c[i+1].x&&c[i].y==c[i+1].y)
            continue;
        b[++l]=c[i];
    }
    /*for(ll i=1;i<=l;i++)
        cout<<b[i].x<<' '<<b[i].y<<endl;*/
    for(ll i=1;i<=l;i++)
        d[i]=M;
    ll t=0;
    for(ll i=1;i<=l;i++)
    {
        bool f=false;
        if(b[i].x==b[i+1].x)
        {
            t++;
            while(b[i].x==b[i+1].x)
            {
                d[t]-=b[i].y;
                d[t]=(d[t]%K+K)%K;
                i++;
                f=true;
            }
            if(f)//这个就是如果第i位和第i+1位相同，再把第i+1位也减去
            {
                d[t]-=b[i].y;
                d[t]=(d[t]%K+K)%K;
            }
        }
        else
            d[++t]-=b[i].y;
    }
    ll h=work(m-t);
    ll ans=1;
    for(ll i=1;i<=t;i++)
        ans*=d[i],ans%=K;
    ans=(ans*h%K+K)%K;
    cout<<ans<<endl;
    return 0;
}