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

Ural SU contest. Petrozavodsk training camp. Winter 2006

About     Problems     Submit solution     Judge status     Standings
Contest is over

D. 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.

Input

The integer 3 ≤ N ≤ 70000.

Output

Output the number of bars in each of the safes.

Sample

inputoutput
3
4
Problem Author: Alexander Ipatov
Problem Source: Ural SU Contest. Petrozavodsk Winter Session, January 2006
To submit the solution for this problem go to the Problem set: 1462. Uncle Scrooge's Gold