e-olymp
Competitions

Azerbaijan Programming Olympiad - 2nd Stage preparation

Домино

Написать программу, которая подсчитает количество вариантов покрытия прямоугольника 2 × n прямоугольниками 2 × 1. Покрытия, которые превращаются сами в себя симметриями считать разными.

Входные данные

Одно число n (0 < n < 65536).

Выходные данные

Вывести искомое количество вариантов.

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 X Всеукраинская олимпиада по информатике, 1997 г.