스카이라인

새 영화의 감독은 촬영을 위한 축소 세트를 만들어야 한다. 세트에는 $N$개의 고층 건물이 있으며, 각 건물의 높이는 $1$부터 $N$미터까지 서로 다른 정수이다. 스카이라인은 왼쪽에서 오른쪽으로 늘어선 건물들의 높이 수열로 정해지며, 이는 $1$부터 $N$까지의 정수의 순열이 된다.

감독은 매우 까다로워서 특정한 '오르막' 형태를 피하고 싶어 한다. 구체적으로, 위치 $i, j, k$ $(i < j < k)$에 있는 세 건물 중 건물 $i$의 높이가 건물 $j$의 높이보다 작고, 건물 $j$의 높이가 건물 $k$의 높이보다 작은 경우가 단 하나도 없기를 바란다.

주어진 건물 수에 대해, 감독이 싫어하는 이 오르막 형태를 피하는 서로 다른 스카이라인 배열이 몇 가지인지 구하여라.

입력에는 여러 개의 테스트 케이스가 주어진다. 각 테스트 케이스는 고층 건물의 수를 나타내는 하나의 정수 $N$ $(3 \le N \le 1{,}000)$이 적힌 한 줄로 이루어진다. 건물들의 높이는 $1, 2, 3, \dots, N$이라고 가정한다. 입력은 하나의 $0$이 적힌 줄로 끝난다.

각 테스트 케이스마다, 감독이 싫어하는 오르막 형태를 피하는 좋은 스카이라인의 수를 $1{,}000{,}000$으로 나눈 나머지를 하나의 정수로 출력한다. 각 정수는 공백 없이 한 줄에 하나씩 출력하며, 답 사이에 빈 줄을 넣지 않는다.