시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 0 0 0 0.000%

문제

벽에 서로 다른 못 두 개가 나란히 박혀 있다. 이 못들에 실 한 가닥을 여러 번 아무렇게나 감는다. 그러고 나서 실 양쪽 끝을 액자에 묶는다. 액자가 실에 매달려 있다면 성공이다.

여기서 조건을 하나 더 추가해 보자. 두 못 중 하나를 빼면 실이 풀려 액자가 떨어져야 한다는 것이다. 즉, 첫째 못을 빼도 액자가 떨어지고, 첫째 못을 가만히 두고 둘째 못을 빼도 떨어져야 한다. 이러한 조건을 만족하도록 실을 감는 방법은 무한히 많다.

위 그림은 조건을 만족하도록 실을 감는 방법 중 감은 횟수가 4회로 가장 적은 서로 다른 8가지이다. 맨 왼쪽 위의 경우는 실을 잡고 왼쪽 못에 반시계 방향으로 감은 후, 오른쪽 못에 시계 방향으로 감고, 왼쪽 못에 시계 방향으로 감고, 오른쪽 못에 반시계 방향으로 감은 모양이다. 즉, 감은 횟수는 4회이고 감은 순서는 (왼쪽, 반시계), (오른쪽, 시계), (왼쪽, 시계), (오른쪽, 반시계)이다.

왼쪽 못을 빼면 실이 위와 같이 감겨 있는 것이나 마찬가지가 된다. 따라서 실이 풀려 액자가 떨어지게 된다. 오른쪽 못을 빼도 마찬가지로 액자가 떨어진다.

이제 이 문제를 n개의 못으로 확장한다. 즉, n개의 서로 다른 못에 실을 감는다. n개의 못 중 아무거나 하나를 빼도 액자가 떨어져야 한다. 이때 조건을 만족하도록 실을 감는 방법 중 감은 횟수의 최솟값을 m이라 하자. 조건을 만족하도록 실을 감는 방법 중 감은 횟수가 m인 방법의 수를 구하는 프로그램을 작성하시오. 단, 답이 매우 커질 수 있으므로 10^9 + 7로 나눈 나머지를 출력한다. 못의 개수 n은 2 이상 10의 5제곱 이하의 자연수이다.

입력

첫째 줄에 정수 n이 주어진다.

출력

감은 횟수가 최소가 되도록 조건을 만족하도록 실을 감는 방법의 수를 109 + 7로 나눈 나머지를 출력한다.

예제 입력 1

2

예제 출력 1

8

예제 입력 2

5

예제 출력 2

4096

예제 입력 3

22892

예제 출력 3

12471882