지그재그 줄세우기

문제 제목: 지그재그 줄세우기

N명의 학생이 있으며, 각 학생은 1번부터 N번까지 번호가 매겨져 있다. 번호가 작을수록 키가 작고, 번호가 클수록 키가 크다. 이 학생들을 다음 규칙에 따라 한 줄로 세우려고 한다.

1. 첫 번째 자리와 두 번째 자리에는 아무 학생이나 설 수 있다.
2. 세 번째 자리부터는 다음 조건을 만족하는 학생만 설 수 있다. 바로 앞에 선 학생이 그 앞 학생보다 키가 크다면, 새로 설 학생은 바로 앞 학생보다 키가 작아야 한다. 반대로 바로 앞에 선 학생이 그 앞 학생보다 키가 작다면, 새로 설 학생은 바로 앞 학생보다 키가 커야 한다.

즉, 줄을 선 임의의 인접한 세 명의 키는 증가, 감소, 증가... 또는 감소, 증가, 감소... 형태로 번갈아 나타나야 한다. 이를 '지그재그 수열'이라고 부른다.

N명의 학생을 위 규칙에 따라 한 줄로 세우는 경우의 수를 1,000,000으로 나눈 나머지를 구하라.

입력

첫째 줄에 학생의 수 N이 주어진다.

출력

N명의 학생을 규칙에 맞게 한 줄로 세우는 경우의 수를 1,000,000으로 나눈 나머지를 출력하라.

제한

• 1 ≤ N ≤ 100

입출력 예시

입력 1

5

출력 1

32