#include<iostream>  
#include<cstdio>  
#include<ctime>  
#include<cstring>  
#include<cstdlib>  
#include<vector>  
#define LL  __int64 
using namespace std;  
LL PowMod(LL a,LL b,LL MOD){  //费马小定理求逆元
    LL ret=1;  
    while(b){  
        if(b&1) ret=(ret*a)%MOD;  
        a=(a*a)%MOD;  
        b>>=1;  
    }  
    return ret;  
}  
LL fac[100005];  
LL Get_Fact(LL p){  
    fac[0]=1;  
    for(LL i=1;i<=p;i++)  
        fac[i]=(fac[i-1]*i)%p;  //预处理阶乘 
}  
LL Lucas(LL n,LL m,LL p){  
    LL ret=1;  
    while(n&&m){  
        LL a=n%p,b=m%p;  
        if(a<b) return 0;  
        ret=(ret*fac[a]*PowMod(fac[b]*fac[a-b]%p,p-2,p))%p;  
        n/=p;  
        m/=p;  
    }  
    return ret;  
}  
int main(){  
    int t;  
    scanf("%d",&t);  
    while(t--){  
        LL n,m,p;  
        scanf("%I64d%I64d%I64d",&n,&m,&p);  
        Get_Fact(p);  
       
        printf("%I64d\n",Lucas(n,m,p));  
    }  
    return 0;  
}  
/*
卢卡斯定理
O(logp(n)) 
*/

或者

#include <iostream>
#include <cmath>
#define ll unsigned long long int
const ll mod=1000000007;
using namespace std;
ll pow(ll a,ll b )//用迭代法求快速幂a^b%mod，即逆元
{
    ll ans=1,ret=a;
    while(b)
    {
        if(b&1) ans=ans*ret%mod;
        ret=ret*ret%mod;
        b>>=1;
    }
    return ans;
}
ll c(ll n,ll m)//用费马小定理求c（n,m)
{
    ll fac=1;
    for(ll i=1;i<=m;i++)
    {
        fac=fac*(n-m+i)%mod;
        fac=fac*pow(i,mod-2)%mod;//每一次都要求快速幂，这样最后就是m！的mod-2次方了，也可先求之前列出的费马小定理的公式的左半部分的阶乘，再求右半部分阶乘的快速幂
    }
    //cout<<fac<<endl;
    return fac;
}
ll lucas(ll n,ll m)
{
    if(m==0) return 1;
    return c(n%mod,m%mod)*lucas(n/mod,m/mod)%mod;
}
int main()
{
    ll n,sum1=0,sum2=0,sum=0;
    scanf("%lld",&n);
        sum1=lucas(n,4);
        sum2=lucas(n,2);
        //cout<<sum1<<" "<<sum2<<endl;
        sum=(sum1+sum2+1-n+mod)%mod;//减法取模
        printf("%lld\n",sum);
    return 0;
}