题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4828

Problem Description

　　度度熊最近很喜欢玩游戏。这一天他在纸上画了一个2行N列的长方形格子。他想把1到2N这些数依次放进去，但是为了使格子看起来优美，他想找到使每行每列都递增的方案。不过画了很久，他发现方案数实在是太多了。度度熊想知道，有多少种放数字的方法能满足上面的条件？

 

 

Input

　　第一行为数据组数T(1<=T<=100000)。
　　然后T行，每行为一个数N(1<=N<=1000000)表示长方形的大小。

 

 

Output

　　对于每组数据，输出符合题意的方案数。由于数字可能非常大，你只需要把最后的结果对1000000007取模即可。

 

 

Sample Input


 

2 1 3

 

 

Sample Output


 
Case #1: 1 Case #2: 5

Hint

对于第二组样例，共5种方案，具体方案为：

题目大意：中文题，容易理解，

之前见过一个题，小朋友排队，说是n个小朋友1~n，排成两排，要求和题目一样，卡特兰数完成的，因此我只个直接就用卡特兰数了。

卡特兰数的递推式：f[n]=f[n-1]*(4*n-2)/(n+1);

注意一点就是卡特兰数取模的时候要用费马小定理转换一下，否则会爆精度，使用费马小定理过程如下：

(a/b)%mod = (a/b)*1%mod = (a/b)*b^(mod-1)%mod = a*b^(mod-2)%mod;

直接从除法变成了乘法，用快速幂进行b的mod-2次方 的运算，这样就能保证精度了

ac:

#include<stdio.h>
#include<string.h>  
#include<math.h>  
  
#include<map>   
//#include<set>
#include<deque>  
#include<queue>  
#include<stack>  
#include<bitset> 
#include<string>  
#include<iostream>  
#include<algorithm>  
using namespace std;  

#define ll long long  
#define INF 0x3f3f3f3f  
#define mod 1000000007
//#define max(a,b) (a)>(b)?(a):(b)
//#define min(a,b) (a)<(b)?(a):(b) 
#define clean(a,b) memset(a,b,sizeof(a))// 水印 
//std::ios::sync_with_stdio(false);

ll f[1000100];

ll quick(ll x,ll n)
{
	ll res=1;
	while(n)
	{
		if(n&1)
			res=(res*x)%mod;
		x=(x*x)%mod;
		n=n>>1;
	}
	return res;
}

void intt()
{
	f[1]=1;
	for(int i=2;i<1000100;++i)
	{
		f[i]=(f[i-1]*(4*i-2))%mod;
		f[i]=f[i]*quick(i+1,mod-2)%mod;
	}
}

int main()
{
	intt();
	int T,Case=1;
	cin>>T;
	while(T--)
	{
		ll n;
		cin>>n;
		/*
		卡特兰数 
		f[n]=f[n-1]*(4*n-2)/n+1;
		
		*/
		cout<<"Case #"<<Case++<<":"<<endl<<f[n]%mod<<endl;
	}
}