Skyline

The director of a new movie needs to build a scaled-down set for the film. The set will contain $N$ skyscrapers whose heights are distinct integers from $1$ to $N$ meters. The skyline is the sequence of the buildings' heights read from left to right, so it is a permutation of the integers from $1$ to $N$.

The director is extremely meticulous and wants to avoid one particular rising pattern: she does not want ANY three buildings at positions $i, j, k$ with $i < j < k$ such that the height of building $i$ is smaller than that of building $j$ and the height of building $j$ is smaller than that of building $k$.

For a given number of buildings, determine how many distinct skyline orderings avoid the rising pattern she dislikes.

The input contains several test cases. Each test case is a single line containing one integer $N$ $(3 \le N \le 1{,}000)$, the number of skyscrapers. Their heights are assumed to be $1, 2, 3, \dots, N$. The input ends with a line containing a single $0$.

For each test case, output a single integer: the number of good skylines — those that avoid the rising pattern the director dislikes — modulo $1{,}000{,}000$. Print each integer on its own line with no spaces, and do not print any blank lines between answers.