How Many Unicycles in a Wheel?

Time limit1sMemory limit512 MB

Summary

Count the number of spanning unicycles (spanning trees plus one edge forming a single cycle) in a wheel graph of size m, output modulo 100007.

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

Problem

A wheel graph of size $n$ is a cycle of $n$ vertices, each of which is connected to a center vertex. Examples of wheel graphs of size 4, 5, 6, and 8 are shown below.

A spanning unicycle in a graph $G$ is a spanning tree in $G$ with one additional edge added to form a single cycle. Each of the examples below is a spanning unicycle in a wheel graph of size 5.

Write a program to compute the number of different unicycles in a wheel graph of size $n$ . Recall that two subgraphs $S_1$ and $S_2$ of a graph $G$ are different if there is at least one edge of $G$ that is in $S_1$ and not in $S_2$ , or an edge in $S_2$ which is not in $S_1$ .

Input

Input consists of a single line that contains a decimal integer $m$ ( $3 \le m \le 4000$ ), which is the size of the wheel graph to find the number of unicycles of.

Output

The single output line consists of the count of unicycles modulo $100007$ for the input size $m$ .

Examples2

Example 1
Input
```
5
```
Expected output
```
170
```
Example 2
Input
```
1234
```
Expected output
```
17511
```