ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

1462. Uncle Scrooge's Gold

Time limit: 1.0 second
Memory limit: 64 MB
Uncle Scrooge manufactured many gold bars and numbered them with sequences of zeros and ones of length 2N-2 (each bar's number is stamped on it). It is known that
  1. Any two bars have different numbers.
  2. The number of any bar does not contain two successive zeros.
  3. For any sequence with property 2, there is a bar with this number in Uncle Scrooge's collection.
Then Uncle Scrooge decided to put his gold bars to safes. The codes for the safes are selected similarly to the numbers of the bars. Namely,
  1. A code for a safe is a sequence of zeros and ones of length N-2.
  2. Codes for any two safes are different.
  3. The code for any safe does not contain two successive zeros.
  4. For any code with properties 1 and 3, there is a safe with this number in Uncle Scrooge's depository.
Uncle Scrooge put in each of the safes the same number of gold bars. As for the remaining bars (there are less of them than the safes), he decided to give them for charity. You should find the number of gold bars in each of Uncle Scrooge's safes.


The integer 3 ≤ N ≤ 70000.


Output the number of bars in each of the safes.


Problem Author: Alexander Ipatov
Problem Source: Ural SU Contest. Petrozavodsk Winter Session, January 2006