Graph Matching

Time limit1sMemory limit128 MB

Summary

Count the number of matchings (independent edge sets) of the cycle graph C_n for each given n, likely requiring big-integer arithmetic via a Lucas-sequence style recurrence.

Level: Medium5 of 10
Topics: Dynamic programming, Math, Combinatorics
Solved: No attempts yet

Problem

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$ .

Input

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$ )

Output

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

Examples4

Example 1
Input
```
3
4
100
```
Expected output
```
4
7
792070839848372253127
```
Example 2
Input
```
3
```
Expected output
```
4
```
Example 3
Input
```
4
```
Expected output
```
7
```
Example 4
Input
```
3
4
5
6
7
8
```
Expected output
```
4
7
11
18
29
47
```