|
Asif is a student of East West University and he is currently working for the EWUISP to meet his relatively high tuition fees. One day, as a part of his job, he was instructed to connect cable wires to N houses. All the houses lie in a straight line. He wants to use only the minimum number of cable wires required to complete his task such that all the houses receive the cable service. A house can either get the connection from the main transmission center or it can get it from a house to its immediate left or right provided the latter house is already getting the service.
You are to write a program that determines the number of different combinations of the cable wires that is possible so that every house receives the service.
Example: If there are two houses then 3
combinations are possible as shown in the figure.
Figure: circles represent the transmission center and the small rectangles
represent the houses.
Input
Each line of input contains a positive integer N (N<=2000). The meaning of N is described in the above paragraph. A value of 0 for N indicates the end of input which should not be processed.
Output
For each line of input you have to output, on a single line, the number of possible arrangements. You can safely assume that this number will have less than 1000 digits.
Sample Input
|
1 |
Sample Output
|
1 |
Problem Setter: Sohel Hafiz