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 2 3 0 Sample Output 1 3 8