K

K. Рекурсивные числа Фибоначчи

У Тимофея было n(0 ≤ n ≤ 32) стажёров. Каждый стажёр хотел быть лучше своих предшественников, поэтому i-й стажёр делал столько коммитов, сколько делали два предыдущих стажёра в сумме. Два первых стажёра были менее инициативными —– они сделали по одному коммиту.

Пусть F_i —– число коммитов, сделанных i-м стажёром (стажёры нумеруются с нуля). Тогда выполняется следующее: F₀ = F₁ = 1. Для всех i ≥ 2 выполнено F_i = F_i−1 + F_i−2.

Определите, сколько кода напишет следующий стажёр –— найдите F_n.

Решение должно быть реализовано рекурсивно.

Формат ввода

На вход подаётся n — целое число в диапазоне от 0 до 32.

Формат вывода

Нужно вывести F_n.

Пример 1

Ввод	Вывод
3	3

Пример 2

Ввод	Вывод
0	1