깨진 휠 그래프에서 유니사이클 개수 세기

크기 n의 휠 그래프(Wheel Graph)는 정점이 n개인 순환(cycle)이며, 정점은 v[1], …, v[n]이고 각 정점은 중심 정점 v[0]과 연결되어 있다. 크기 4, 5, 6, 8인 휠 그래프의 예는 아래와 같다.

크기 n의 깨진 휠 그래프(Broken Wheel Graph)는 크기 n의 휠 그래프에서 v[n]과 v[1]을 잇는 간선을 제거한 그래프이다. 크기 4, 5, 6, 8인 깨진 휠 그래프의 예는 아래와 같다.

그래프 G에서 전역 유니사이클(spanning unicycle)은 G의 신장 트리에 간선을 하나 더해 정확히 하나의 사이클을 만든 부분 그래프이다. 아래 그림은 크기 5인 깨진 휠 그래프에서의 전역 유니사이클 예이다.

크기 n의 깨진 휠 그래프에서 서로 다른 유니사이클의 개수를 구하는 프로그램을 작성하라. 그래프 G의 두 부분 그래프 S1, S2는 S1에는 있고 S2에는 없는 간선이 있거나, S2에는 있고 S1에는 없는 간선이 있으면 서로 다르다.

입력은 한 줄이며, 정수 m (3 ≤ m ≤ 4000)이 주어진다. m은 유니사이클의 개수를 구할 휠 그래프의 크기이다.

한 줄에 유니사이클의 개수를 100007로 나눈 나머지를 출력한다.