Uncle Scrooge's Gold#4946

Uncle Scrooge's Gold

1 second
128 megabytes
Easy

Uncle Scrooge made a lot of gold bars and numbered them with sequences of zeros and ones of length 2n - 2 (the number of each ingot is stamped on it). It is known that:

  1. Any two ingots have different numbers.

  2. In the number of any ingot there are no two zeros in a row.

  3. For any sequence corresponding to the property , there is an ingot with such number in the Uncle Scrooge's collection.

Then Uncle Scrooge decided to put the bars into safes. Codes for safes are matched in a similar way to numbers of ingots. Namely:

  1. The code to the safe is a sequence of zeros and ones of length n - 2.

  2. The codes for any two safes are different.

  3. There is no safe with a code that contains two zeros in a row.

  4. For any code that corresponds to the properties and , the safe with this code is in the Uncle Scrooge's store.

Uncle Scrooge put in each safe the same number of gold bars, and the remaining ingots (they were left less than safes) decided to send to charity. Find how many ingots are in each of the safes of Uncle Scrooge.

Input

One integer (3 \le n \le 70000).

Output

Print the number of gold bars in each safe.

Examples

Example 1

Loading
Loading