지그재그 서기

서로 키가 다른 N명의 학생을 한 줄로 세운다. 학생은 키가 작은 순서대로 1부터 N까지 번호가 붙어 있으며, 모든 학생은 정확히 한 번씩 서야 한다.

첫 번째 자리와 두 번째 자리에는 아무 학생이나 설 수 있다. 세 번째 자리부터는 바로 앞의 두 학생을 비교해 다음 학생의 방향이 정해진다.

• 바로 앞 학생이 그 앞 학생보다 크면, 다음 학생은 바로 앞 학생보다 작아야 한다.
• 바로 앞 학생이 그 앞 학생보다 작으면, 다음 학생은 바로 앞 학생보다 커야 한다.

즉, 인접한 두 학생 사이의 대소 관계가 매 자리마다 번갈아 나타나야 한다. 예를 들어 5명의 학생을 세울 때 1 - 3 - 2 - 5 - 4나 3 - 2 - 5 - 1 - 4는 조건을 만족한다.

N명의 학생을 조건에 맞게 세우는 방법의 수를 구하라.

첫째 줄에 학생 수 N이 주어진다. (1 <= N <= 100)

조건을 만족하는 줄 세우기의 수를 1,000,000으로 나눈 나머지를 출력한다.