How Many Unicycles in a Broken Wheel
시간 제한1초메모리 제한1024 MB
크기가 m인 깨진 바퀴 그래프에서 신장 유니사이클(신장 트리에 간선 하나를 더한 것)의 개수를 100007로 나눈 나머지를 구한다.
문제
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.