How Many Unicycles in a Broken Wheel

문제

A Wheel Graph of size n is a cycle of n vertices, v[1], …, v[n] each of which is connected to a center vertex, v[0]. Examples of wheel graphs of size 4, 5, 6 and 8 are shown below:

A Broken Wheel Graph of size n is a wheel graph of size n with the edge from v[n] to v[1] removed. Examples of broken 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 broken wheel graph of size 5:

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

입력

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

출력

The single output line consists of the count of unicycles modulo 100007.

5

19

1234

50380