Кузнечик прыгает по столбикам, расположенным на одной линии на равных расстояниях друг от друга. Столбики имеют порядковые номера от 1 до N . В начале Кузнечик сидит на столбике с номером 1. Он может прыгнуть на следующий столбик или сразу на второй столбик, считая от текущего. Требуется найти количество способов, которыми Кузнечик может добраться до столбика с номером N . Учитывайте, что Кузнечик не может прыгать назад.
Входные данные
Входная строка содержит натуральное число N ( 1 ≤ N ≤ 45 ).
Выходные данные
Программа должна вывести одно число: количество способов, которыми Кузнечик может добраться до столбика с номером N .