题目描述

𝑛（3≤𝑛≤10000）个结点组成一个圈，求匹配（即没有公共点的边集）的个数。比如𝑛=4时有7个（如下图),𝑛=100时有792070839848372253127个。

环图𝐶𝑛(𝑛≥3)是一个简单无向图,其顶点集为1,...,𝑛 包含𝑛条边。下图描绘了图𝐶3、𝐶4、𝐶5和𝐶6。

图𝑎:𝐶4的匹配。属于相应匹配的边用绿色表示,而未包含在匹配中的边用虚线表示。𝑀1=∅,𝑀2=2,1,𝑀3=3,2,𝑀4=4,3,𝑀5=1,4,𝑀6=2,1,4,3

输入格式

每行输入包含一个正整数：𝑛，其中3≤𝑛≤10000。

输出格式

对于每行输出，一行包含𝐶𝑛中的匹配数。

3
4
100

4
7
792070839848372253127