问题描述 
有一个机器人位于坐标原点上。每秒钟机器人都可以向右移到一个单位距离，或者在原地不动。如果机器人的当前位置在原点右侧，它同样可以
向左移动单位距离。一系列的移动（左移，右移，原地不动）定义为一个路径。问有多少种不同的路径，使得nnn秒后机器人仍然位于坐标原点？
答案可能很大，只需输出答案对1,000,000,0071,000,000,0071,000,000,007的模。
输入描述 
输入包含多组数据. 第一行有一个整数T(1≤T≤100)T (1\leq T\leq 100)T(1≤T≤100), 表示测试数据的组数. 对于每组数据:
输入一个整数 n(1≤n≤1,000,000)n (1\leq n\leq 1,000,000)n(1≤n≤1,000,000)。
输出描述 
对于每组数据，输出一个整数
输入样例 
3
1
2
4
输出样例 
1
2
9

【解题方法】知道了这个是个默慈金数，并知道它的递推式，就可以了，这题我先用java，被卡内存了，只能选择求逆元的方法，预处理1000000以内的默慈金数。

【AC代码】

//cpp
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
const int N = 1000003;
const int MOD = 1000000007;
typedef long long LL;
LL ans[N];
LL pow_mod(LL a,LL n,LL mod){
   LL res = 1;
   while(n){
        if(n&1){
            res = (res*a)%MOD;
        }
        a = (a*a)%MOD;
        n>>=1;
   }
   return res;
}
int main(){
    int T,n;
    ans[0]=1;
    ans[1]=1;
    for(int i=2; i<N; i++){
        ans[i] = ((2*i+1)*ans[i-1]+3*(i-1)*ans[i-2])%MOD*pow_mod(i+2,MOD-2,MOD)%MOD;
    }
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        printf("%I64d\n",ans[n]);
    }
    return 0;
}