17358번 - 복불복으로 지구 멸망

문제

오늘은 즐거운 선린 축제날, 갑자기 폭우가 쏟아지기 시작했다! 상민이는 비에 실망한 학우들을 위해 실내에서도 할 수 있는 복불복 게임을 준비했다.

상민이는 N개의 컵에 N개의 서로 다른 음료를 담았다. 그러고는 아래와 같은 규칙에 따라 음료를 섞기로 했다.

1. 1~N의 번호가 메겨진 컵을 오름차순으로 일렬로 배치한다.
2. 어떤 두 컵을 골라 위치를 맞바꾼다. 이 작업을 N/2번 반복한다.
3. 모든 컵은 정확히 한 번씩 위치가 바뀌어야 한다. 자기 자신과는 위치를 바꿀 수 없다.

이쯤 읽고 나니 왠지 컵이 배열되는 경우의 수가 몇 가지인지 궁금해야 할 것 같다. 이걸 구하지 않으면 지구가 멸망한다고 한다. 이 문제를 풀고 지구의 용사가 되자!

입력

첫째 줄에 음료의 개수 N이 주어진다. N은 항상 짝수이다. (2 ≤ N ≤ 10⁵)

출력

컵이 배열되는 경우의 수를 출력한다. 수가 커질 수 있으므로 10⁹+7로 나눈 나머지를 출력한다.

제한

힌트