Graph Matching

In graph theory, a matching (or independent edge set) is a set of edges no two of which share a common vertex.

Given a graph $G = (V, E)$, a set $M$ is a matching of $G$ if $M \subseteq E$ and no two edges in $M$ share a vertex. The empty set also counts as a matching.

The cycle graph $C_n$ ($n \ge 3$) is a simple undirected graph with vertex set ${1, 2, \dots, n}$ and edge set $E(C_n) = {{a, b} \mid a - b \equiv \pm 1 \pmod n}$. In other words, its $n$ vertices are joined into a single ring by connecting neighboring vertices; it is a $2$-regular graph with exactly $n$ edges.

Write a program that computes the number of matchings of the cycle graph $C_n$.

The input consists of several test cases. Each test case is a single integer $n$, given one per line, until the end of the input. ($3 \le n \le 10000$)

For each test case, print the number of matchings of $C_n$, one per line.