SKYLINE  Skyline
The director of a new movie needs to create a scaled set for the movie. In the set there will be N skyscrapers, with distinct integer heights from 1 to N meters. The skyline will be determined by the sequence of the heights of the skyscrapers from left to right. It will be a permutation of the integers from 1 to N.
The director is extremely meticulous, so she wants to avoid a certain sloping pattern. She doesn’t want for there to be ANY three buildings in positions i, j and k, i < j < k, where the height of building i is smaller than that of building j, and building j’s height is smaller than building k’s height.
Your task is to tell the director, for a given number of buildings, how many distinct orderings for the skyline avoid the sloping pattern she doesn't like.
Input
There will be several test cases in the input. Each test case will consist of a single line containing a single integer N (3 ≤ N ≤ 1,000), which represents the number of skyscrapers. The heights of the skyscrapers are assumed to be 1, 2, 3, ..., N. The input will end with a line with a single 0.
Output
For each test case, output a single integer, representing the number of good skylines  those avoid the sloping pattern that the director dislikes  modulo 1,000,000. Print each integer on its own line with no spaces. Do not print any blank lines between answers.
Example
Input:
3
4
0
Output:
5
14
hide comments
nikhil1234hnd:
20231213 15:04:09
i came to known that catalan numbers will help here but i am not able to relate catalan number concept to this question can anybody help me. how i can know i should use catalan numbers here


hori_josu2002:
20231105 03:35:50
Can someone Help me with this :CC


yasser1110:
20210514 13:47:01
Such a poor question. If you know x, you will easily be able to solve, otherwise keep struggling. search for x. 

codephilic:
20201004 13:52:06
See the modulo carefully !! 

linkret:
20200906 20:57:31
preach brother 

nadstratosfer:
20180418 14:37:08
You know the problem is from an american contest when the movie director is a "she". Because, if we only repeat feminist slogans often and aggresively enough, the she's will stop uploading selfies or calling everything rape, and flood us with Godfather's and other Taxi Driver's. In the meantime, the most recent US team ICPC triumph was 20 years ago. And look at these horribly not diverse countries they keep losing to... Technology > ideology. 

vivace:
20161215 19:16:49
discrete mathematics :D 

MishThi:
20151025 19:31:17
@Ankit Kumar : Plz dont post solutions! 

MishThi:
20151023 09:02:20
Great problem. Learnt a few new concepts.


Aayush:
20150107 11:25:18
Getting "internal error" with python 3.4..

Added by:  Iqram Mahmud 
Date:  20101117 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  ACM ICPC Southeast USA Regional 2010 