这道题好像我没有用卢卡斯。

个人使用的方法是扩欧和有理数取余。

已经ac，但是在某一个常数那里有问题。

50分

（把第 $4$ 行的 $m$ 改成$10007×10007$就100分了。）

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a,b,n,i,j,ans=3,m=10007*107,x=1;
long long crt(long long x,long long y,long long z)
{
	if(z%x==0) return z;
	return crt(y%x,x,(((x-z)%x)+x)%x)/(y%x)*y+z;
}
long long gcd(long long c1,long long c2)
{
	return c2==0?c1:gcd(c2,c1%c2);
}
int main()
{
	cin>>n;
    for(i=1;i<=(n-1)/2;i++)
    {
        x=x*(n-i)%m;
        x=(crt(m,i%m,m-x)-m+x)/(i%m);
        if(n%2==1&&i==(n-1)/2) ans=(ans+x*n)%10007;
        else ans=(ans+x*(4*i+3))%10007;
    }
    cout<<ans;
	return 0;
}

有没有大佬能解释一下为什么？