链接：https://www.nowcoder.com/acm/contest/85/I
题目描述
あなたの蛙が帰っています！
蛙蛙完成了一趟旅行，回家啦！但它还是没有去它心中非常想去的几个地方。总共有 N 个它 想去的目的地。蛙蛙下定了决心，它要做一个愿望清单，一定要让自己去那些想去的地方。蛙蛙 是这样做的：它会不定时地想起一个或多个目的地，然后按顺序写在愿望清单上。但是每次蛙蛙 出去旅行时，都会先去最近写在愿望清单上的地方，并且蛙蛙不会重复去一个目的地，但它会去 访问所有的目的地。蛙蛙有个最想去的地方，这个地方是它第一个想到的，但由于种种原因，这 个地方不能是第一个被蛙蛙访问的。蛙蛙脑中回想目的地的顺序是固定的，所以它想请问你，它最终访问这些目的地的顺序有多少种？
对于两种访问序列 
和 
，它们是不同的当且仅当存在至少一个 
，使得 
。
为了让大家不被卡题意，这里给出一句话题意：已知一个没有深度限制的栈的入栈序列为，且
不能第一个出栈。求合法的出栈序列个数。答案对
取模。
输入描述:
第一行一个数
，表示蛙蛙有
组询问。
接下去
行，每行一个正整数
， 表示目的地的个数（入栈元素个数）。
输出描述:
输出共
行，每行一个答案，格式形如
，具体可见样例。
答案可能较大，请对
取模后输出。
输入例子:
3
3
9
24
输出例子:
Case #1: 3
Case #2: 3432
Case #3: 508887030
-->
示例1
备注:
相关知识传送门：
AC代码:
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <time.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <iostream>
#include <deque>
#include <set>
#include <bitset>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const int N = 2e5+;
const ll mod = ;
ll fac[N]; void extgcd(ll a,ll b,ll& d,ll& x,ll& y){
if(!b){ d=a; x=; y=;}
else{ extgcd(b,a%b,d,y,x); y-=x*(a/b); }
}
ll inv(ll a,ll n){
ll d,x,y;
extgcd(a,n,d,x,y);
return d==?(x+n)%n:-;
} void init() {
fac[] = fac[] = ;
for(int i = ; i < N; ++i) {
fac[i] = fac[i-]*i%mod;
}
}
ll cat(ll n) {
return fac[*n]*inv(fac[n+]*fac[n],mod)%mod;
}
int main(int argc, char *argv[]) {
init();
int T;
int ca = ;
scanf("%d", &T);
while(T--) {
ll n;
cin >> n;
ll ans = (cat(n)-cat(n-))%mod;
if(ans < ) ans += mod;
printf("Case #%d: ", ca++);
cout << ans << '\n';
}
}