Proglute

Tomorrow Programming School의 바로크 오페라 애호가들이 실험적인 공연에 쓸 새로운 현악기를 개발하고 있다. 이 악기는 programmed lute, 줄여서 proglute라고 부르며, 평평한 원형 몸통의 둘레에 1부터 N까지 번호가 매겨진 N개의 페그가 있다.

각 줄은 서로 다른 두 페그 사이에 걸리고, 몸통을 가로지르되 다른 줄과 교차하지 않는다. 주 페그(principal peg)라고 부르는 두 페그를 제외한 모든 페그에는 줄이 두 개씩 붙는다. 주 페그에는 줄이 하나만 붙는다.

줄은 연주자가 한쪽 주 페그에서 줄을 짚고 손가락을 떼지 않은 채 모든 줄을 따라 반대쪽 주 페그까지 미끄러뜨릴 수 있도록 배치한다. 손가락은 줄이 끝에서 만나는 페그에서만 다른 줄로 넘어갈 수 있다.

줄의 특성은 양 끝 페그 번호로 이루어진 순서 없는 쌍이다. 악기의 특성은 모든 줄 특성의 집합이다. 특성이 다르면 서로 다른 배치로 본다.

아래 그림은 페그가 다섯 개인 proglute의 가능한 배치 두 가지를 보여준다:

proglute에서 서로 다른 줄 배치의 수를 구하라.

한 줄에 정수 $N$ ($2 \le N \le 1000$)이 주어진다. $N$은 몸통 둘레에 있는 페그의 개수이다.

서로 다른 줄 배치의 수를 $10^9 + 7$로 나눈 나머지를 출력한다.