1146번 - 지그재그 서기

문제

N명의 학생들이 있다. 이 학생들을 다음과 같은 방식으로 줄을 세우려고 한다.

1. 맨 앞줄에는 아무나 설 수 있다.
2. 둘째 줄에도 아무나 설 수 있다.
3. 셋째 줄에는 둘째 줄에 서 있는 사람이 첫째 줄에 서 있는 사람보다 클 경우, 둘째 줄에 서 있는 사람보다 작은 사람만이 설 수 있으며, 둘째 줄에 서 있는 사람이 첫째 줄에 서 있는 사람보다 작을 경우, 둘째 줄에 서 있는 사람보다 큰 사람만이 설 수 있다.
4. 넷째 줄부터는 둘째 줄과 셋째 줄을 비교하는 식으로 해서 N번째의 줄을 서는 사람은 N-2번째 줄과 N-1번째 줄에 서는 사람을 비교해서 세운다.

학생들이 1이 가장 작은 사람, N이 가장 큰 사람이며, 같은 키를 가진 사람이 없다고 할 때, 5명을 세운다면 1 - 3 - 2 - 5 - 4, 3 - 2 - 5 - 1 - 4 등의 방법으로 세울 수 있다.

문제는 N명의 학생을 이런 식으로 줄을 세울 때 총 몇 가지의 경우의 수가 생기는지 찾아내는 것이다.

입력

첫째 줄에 학생 수 N(1 ≤ N ≤ 100)이 입력된다.

출력

첫째 줄에 총 경우의 수를 1,000,000으로 나눈 나머지를 출력한다.

제한

힌트