## SKYLINE - Skyline

no tags

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:340Output:514`

## Code Examples

### #1 Code Example with Python Programming

```Code - Python Programming```

``````cat = [[0 for i in range(1005)] for j in range(1005)]
for i in range(1, 1005):
for j in range(i + 1):
if j == 0:
cat[i][j] = 1
else:
cat[i][j] = (cat[i][j - 1] + cat[i - 1][j]) % 1000000
while True:
N = int(input())
if N == 0:
break
print(cat[N][N])``````
Copy The Code &

Input

cmd
3
4
0

Output

cmd
5
14

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````#include<stdio.h>
int arr[1005][1005]={{0}};
void catalan()
{
int i,j;
for(i=0;i<1005;i++)
{
for(j=0;j<=i;j++)
{
if(j==0)
arr[i][j]=1;
else
arr[i][j]=(arr[i][j-1]+arr[i-1][j])%1000000;
}
}
}
int main()
{
catalan();
int t;
scanf("%d",&t);
while(t)
{
printf("%d\n",arr[t][t]);
scanf("%d",&t);
}
return 0;
}``````
Copy The Code &

Input

cmd
3
4
0

Output

cmd
5
14