Кролик Роджер находится в начале числовой прямой (позиция 0) и хочет добраться до позиции N, где лежит гигантская морковка.
Кролик умеет делать только два вида прыжков:
- Короткий прыжок: +1 позиция (тратит 1 единицу энергии)
- Длинный прыжок: +2 позиции (тратит 1 единицу энергии)
Сколько РАЗЛИЧНЫХ способов есть у Роджера добраться до морковки?
Два способа считаются различными, если последовательность прыжков отличается.
ВХОДНЫЕ ДАННЫЕ:
Одно число N (0 ≤ N ≤ 45) - позиция морковки.
ВЫХОДНЫЕ ДАННЫЕ:
Одно число - количество различных способов добраться до морковки.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
0
|
1
|
|
2
|
5
|
8
|