바퀴 그래프의 단일 사이클 부분 그래프 개수

크기 $n$인 바퀴 그래프(wheel graph)는 $n$개의 정수가 사이클을 이루고, 각 정수가 중심 정수와 연결된 그래프이다. 크기 4, 5, 6, 8인 바퀴 그래프의 예는 다음과 같다.

그래프 $G$의 신장 단일 사이클(spanning unicycle)은 $G$의 신장 트리에 간선 하나를 추가해 사이클 하나를 만든 부분 그래프이다. 다음은 크기 5인 바퀴 그래프의 신장 단일 사이클 예시이다.

크기 $n$인 바퀴 그래프에서 서로 다른 단일 사이클의 개수를 구하는 프로그램을 작성하라. 그래프 $G$의 두 부분 그래프 $S_1$과 $S_2$는 $S_1$에는 속하지만 $S_2$에는 속하지 않는 $G$의 간선이 하나 이상 있거나, $S_2$에는 속하지만 $S_1$에는 속하지 않는 간선이 하나 이상 있으면 서로 다르다.

입력은 한 줄로 주어지며, 단일 사이클의 개수를 구할 바퀴 그래프의 크기를 나타내는 십진 정수 $m$이 포함된다. ($3 \le m \le 4000$)

한 줄에 입력 크기 $m$에 대한 단일 사이클의 개수를 $100007$로 나눈 나머지를 출력한다.