시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 4 | 4 | 3 | 100.000% |
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