(2n个点,就要联想到卡特兰数)
从第一个开始操作点开始编号,1,2,3。。。。
我们发现如果如果连接奇数-奇数,那么必定会有一个偶数点没办法满足题目的连接(即必会交叉)
所以我们一定是奇数-偶数这样连
再深挖下,我们发现交叉都是在始点1-终点1中的点中,有始点的终点>终点1就有交叉,比如(1,4)和(2,5)
所以把始点看出左括号,终点看出是右括号,不交叉就是所有情况都是左括号数量大于右括号数量,然后求方法数——卡特兰数
n有点大,但mod是素数
所以用组合除以的公式
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int mod=1e8+7,N=5e3+3;
ll n;

ll qmi(ll a,ll b){
	ll res=1;
	while(b){
		if(b&1) res*=a,res%=mod;
		b>>=1; a*=a, a%=mod;
	}
	return res;
}
ll C(ll b,ll a){
	ll res=1;
	for(int i=1;i<=a;i++){
		res*=(b-i+1)*qmi(i,mod-2)%mod;
		res%=mod;

	}
	return res;
}

int main(){
	cin>>n;
	cout<<C(n<<1,n)%mod*qmi(n+1,mod-2)%mod;
	return 0;
}