题目链接

【题目描述】

N * N的方格，从左上到右下画一条线。一个机器人从左上走到右下，只能向右或向下走。并要求只能在这条线的上面或下面走，不能穿越这条线，有多少种不同的走法？由于方法数量可能很大，只需要输出Mod 10007的结果。

Input

输入一个数N(2 <= N <= 10^9)。

Output

输出走法的数量 Mod 10007。

Input示例

4

Output示例

10

【思路】

卡特兰数，模数比较小用Lucas定理

#include
    
     using namespace std;typedef long long ll;const int maxn=10010;const int mod=10007;ll pw(ll x,ll n){	ll ans=1;	while(n){		if(n&1) ans=ans*x%mod;		x=x*x%mod;		n>>=1; 	}	return ans;}ll inv(ll a){return pw(a,mod-2);}ll fac[maxn];ll invfac[maxn];void init(){	fac[0]=1;	invfac[0]=1;	for(int i=1;i
     
      n) return 0LL;	ll ans=1LL;	for(;m;n/=mod,m/=mod)		ans=ans*C(n%mod,m%mod)%mod;	return ans;}ll Cat(int n){	return ((Lucas(2*n,n)-Lucas(2*n,n-1))%mod+mod)%mod;}int main(){	init();	int n;	scanf("%d",&n);	printf("%lld\n",2LL*Cat(n-1)%mod);	return 0;}