4222: Cn中的匹配数
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：2
解决：1
题目描述
# Edge Case
## 题目描述
$n（3\le n\le 10000）$个结点组成一个圈，求匹配（即没有公共点的边集）的个数。比如$n=4$时有7个（如上图),$n=100$时有792070839848372253127个。
环图$C_n(n≥3)$是一个简单无向图,其顶点集为${1,...,n}$,包含$n$条边。图$a$描绘了图$C_3、C_4、C_5$和$C_6$。
图$a:C_4$的匹配。属于相应匹配的边用绿色表示,而未包含在匹配中的边用虚线表示。$M_1 = ∅,M_2 = {{2, 1}},M_3 = {{3, 2}},M_4 = {{4, 3}},M_5 = {{1, 4}},M_6 = {{2, 1},{4, 3}}$,以及$M_7 = {{3, 2},{1, 4}}$。
输入
## 输入格式
每行输入包含一个正整数：$n$，其中$3≤n≤10000$。
输出
## 输出格式
对于每行输出，一行包含$C_n$中的匹配数。
样例输入 复制
3
4
100样例输出 复制
4
7
792070839848372253127提示
## 输入输出样例
### 输入样例1
```
3
4
100
```
### 输出样例1
```
4
7
792070839848372253127
```
## 数据范围与提示
$3≤n≤10000$
## 题目来源
ACM/ICPC NWERC 2012