문제

길이 인 순열이란, 부터 까지의 자연수가 한 개씩만 들어간 수열이다. 예를 들어, 은 길이 의 순열이지만, , 등은 길이 의 순열이 아니다.

이 길이 의 순열의 점수는 다음과 같이 정해진다. 임의의 연속한 수 개에 대해 개의 수가 증가하는 순서이거나 감소하는 순서이면 1점을 얻는다. 이 점수의 합을 순열의 점수라고 하자. 예를 들어, 는 , 에서 점씩 얻어서 순열의 점수는 점이 된다. 에서는 점수를 얻을 수 없다.

정수 이 주어진다. 이때, 길이 의 모든 순열에 대한 순열의 점수의 합을 으로 나눈 나머지를 출력하여라.

입력

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

출력

순열의 점수의 합을 으로 나눈 나머지를 한 줄에 출력한다.

예제 설명

첫 번째 예제는 연속한 개의 수를 선택할 수 없으므로 순열의 점수의 합은 이 된다.

두 번째 예제는 각각의 순열에 대해 점수가 다음과 같다.

: 점 (이 증가하는 순서)

: 점

: 점

: 점

: 점

: 점 (이 감소하는 순서)

따라서, 순열의 점수의 합은 가 된다.