N * N的方格，从左上到右下画一条线。一个机器人从左上走到右下，只能向右或向下走。并要求只能在这条线的上面或下面走，不能穿越这条线，有多少种不同的走法？由于方法数量可能很大，只需要输出Mod 10007的结果。
Input
输入一个数N(2 <= N <= 10^9)。
Output
输出走法的数量 Mod 10007。
Input示例
4
Output示例
10 明显是一道卡特兰数，推出ans = C(2*n-2,n-1) * 2 / n % MOD
先让n--,ans = C(2*n,n) * 2 / (n+1) % MOD 这样公式看起来好看些 由于 n <= 10^9,但是 MOD = 10007，所以求ans需要用到lucas定理
//File Name: nod1120.cpp
//Author: long
//Mail: 736726758@qq.com
//Created Time: 2016年05月27日 星期五 15时46分58秒 #include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream> #define LL long long using namespace std; const int MOD = ; LL jie[MOD]; LL qp(LL x,LL y){
LL res = ;
while(y){
if(y & ) res = res * x % MOD;
x = x * x % MOD;
y >>= ;
}
return res;
} void init(){
jie[] = ;
for(int i=;i<MOD;i++)
jie[i] = jie[i-] * i % MOD;
} LL get_c(int x,int y){
if(y == || y == x) return ;
return jie[x] * qp(jie[y] * jie[x-y] % MOD,MOD - ) % MOD;
} LL lucas(LL x,LL y){
LL ans = ;
int u,v;
while(x > || y > ){
u = x % MOD;
v = y % MOD;
ans = ans * get_c(u,v) % MOD;
x /= MOD;
y /= MOD;
}
return ans;
} int main(){
init();
int n;
while(~scanf("%d",&n)){
n--;
printf("%d\n",(int)lucas(*n,n) * qp(n+,MOD-) * % MOD);
}
return ;
}