题目背景

Czyzoiers 都想知道小 x 为什么对鸡蛋饼情有独钟。经过一番逼问，小 x 道出 了实情：因为他喜欢圆。

题目描述

最近小 x 又发现了一个关于圆的有趣的问题：在圆上有2N 个不同的点，小 x 想用 N 条线段把这些点连接起来（每个点只能连一条线段）， 使所有的线段都不想交，他想知道这样的连接方案有多少种？

输入输出格式

输入格式：

 

有且仅有一个正整数 N

 

输出格式：

 

要求的方案数（结果 mod 100000007）。

 

输入输出样例

输入样例#1：

24

输出样例#1：

4057031 把左端点看做入栈，右端点看做出栈 所有线段不相交是一个合法的出栈入栈操作序列 卡特兰数

#include
       
        #define mod 100000007using namespace std;long long f[20000];int main(){    int n;    scanf("%d",&n);    f[0]=f[1]=1;    for(int i=2;i<=n;i++)     for(int j=1;j<=i;j++)      f[i]=(f[i]+f[j-1]*f[i-j]%mod)%mod;    //for(int i=2;i<=n;i++) f[i]=f[i-1]*(4*i-2)/(i+1);    printf("%lld",f[n]);}