先推荐一个关于卡特兰数的博客：http://blog.csdn.net/hackbuteer1/article/details/7450250。
卡特兰数一个应用就是，卡特兰数的第n项表示，现在进栈和出栈的次数都是n次，问最后栈空的合法序列的个数。其他例子见上面这个博客。
那么关于这个题目，我们先选出i次右移的（相当于进栈）次数，i次左移的（相当于出栈）次数，那么当前对答案做出的贡献就是C(n,2*i)*cat[i]，枚举所有的i计算出答案即可。
代码如下：
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
typedef long long ll;
const int N = + ;
const int mod = (int)1e9 + ; int inv[N],cat[N],C[N]; void init()
{
inv[] = ;
for(int i=;i<N;i++) inv[i] = (mod-mod/i) * 1LL * inv[mod % i] % mod; cat[] = cat[] = ;
for(int i=;i<=N/;i++) cat[i] = 1LL* cat[i-] * (*i-) % mod * inv[i+] % mod;
} int main()
{
init();
int T;scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
int ans = ;
C[] = ; // C(n,0) = 1;
for(int i=;i<=n;i++) C[i] = (ll)C[i-] * (n-(i-)) % mod * inv[i] % mod; // O(n)递推组合数C(n,i)
for(int i=;i<=n/;i++) ans = ((ans + (ll)C[i*] * cat[i] % mod) % mod + mod) % mod;
printf("%d\n",ans);
}
return ;
}