시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 189 91 84 56.757%

문제

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

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

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

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

입력

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

출력

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

예제 입력 1

4

예제 출력 1

3

(2,1,4,3), (3,4,1,2), (4,3,2,1) 총 3가지 경우가 가능하다.