e-olymp
Competitions

Azerbaijan Programming Olympiad - 2nd Stage preparation

Domino

Find the number of ways to cover a rectangle 2 × n with domino of size 2 × 1. The coverings that turn themselves into symmetries are considered different.

Input

One integer n (0 < n < 65536).

Output

Print the number of coverings of rectangle.

Time limit 1 second
Memory limit 128 MiB
Input example #1
1
Output example #1
1
Input example #2
4
Output example #2
5
Author Виталий Бондаренко
Source 1997, X All-Ukrainian Informatics Olympiad