首先我按着我的理解说一下它为什么是卡特兰数，首先卡特兰数有一个很典型的应用就是求1~N个自然数出栈情况的种类数。而这里正好就对应了这种情况。我们要满足题目中给的条件，数字应该是从小到大放置的，1肯定在左上角，所以1入栈，这时候我们放2，如果我们把2放在了1的下面就代表了1出栈，把2放在上面就代表了2也进栈（可以看一下hint中第二组样例提示），以此类推，这样去放数，正好就对应了上面一行入栈，下面一行出栈的情况，一共n行，对应上限为n的卡特兰数。
需要注意的地方就是在使用卡特兰数递推式的时候，除法是不遵循同余膜定理的，所以需要用到乘法逆元，设我们要除的数为n，取的膜为mod，那么n的乘法逆元就是，当n与mod互质的时候，通过欧几里得定理n*x + y*mod = gcd(n,m)得到x，将x处理为（x%mod + mod）% mod的形式，就是我们要的乘法逆元。
代码如下：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define maxn 1000010
#define mod 1000000007
#define LL long long
LL ktl[maxn],x,y;
LL exgcd(LL a,LL b)
{
if(b == )
{
x = ;
y = ;
return a;
}
LL gcd = exgcd(b,a%b);
LL tmp;
tmp = x;
x = y;
y = tmp - a/b * y;
return gcd;
}
LL yiyuan(int n)
{
LL gcd = exgcd(n,mod);
if(gcd == )
return (x%mod + mod) % mod;
}
void init()
{
memset(ktl,,sizeof(ktl));
ktl[] = ;
for(int i = ; i <= maxn-; i++)
{
ktl[i] = (ktl[i-]*(*i-)%mod * yiyuan(i+)) % mod;
}
}
int main()
{
int t,n,ca = ;
init();
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
printf("Case #%d:\n",++ca);
printf("%I64d\n",ktl[n]);
}
return ;
}