题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=5673

题意：

有一个机器人位于坐标原点上。每秒钟机器人都可以向右移到一个单位距离，或者在原地不动。如果机器人的当前位置在原点右侧，它同样可以向左移动单位距离。一系列的移动（左移，右移，原地不动）定义为一个路径。问有多少种不同的路径，使得n秒后机器人仍然位于坐标原点？答案可能很大，只需输出答案对1,000,000,007取模。

分析：

最终回到原点说明向左和向右走的步数相同，假设一共走了i步，那么左右各走了i/2步，剩下n−i步则原地等待。

因为只有在原点右边的时候才能向左走，也就是说在走的过程中右边的步数必须大于等于左边的步数，这样我们只需要对于不同的i（i<=n/2)求出其卡特兰数即可。

代码：

#include<cstdio>

#include<iostream>

using namespace std;

typedef long long  ll ;

const int maxn = 1000000 + 5, mod = 1e9 + 7;

ll f[maxn], rf[maxn], inv[maxn];

inline ll C(int n, int m)

{

    if(m < 0||n < m)return 0;

    return f[n] * rf[m] % mod * rf[n - m] % mod;

}

void init()

{

    f[0] = f[1] = rf[0] = rf[1] = inv[0] = inv[1] = 1;

    for(int i = 2; i < maxn; i++){

        f[i] = f[i - 1] * i % mod;

        inv[i] = inv[mod % i] *(mod - mod / i) % mod;

        rf[i] = rf[i - 1] * inv[i] % mod;

    }

}

int main (void)

{

    int T;scanf("%d", &T);

    init();

    while(T--){

        int n;

        scanf("%d", &n);

        ll ans = 0;

        for(int i = 0; i <= n / 2; i++){

          ans += (C(2 * i, i) - C(2 * i, i - 1) + mod )* C(n, 2 * i) % mod;

          ans %= mod;

        }

        printf("%I64d\n", ans % mod);

    }

    return 0;

}