Робот Сильвер занимается терроформированием на планете Шелезяка. Сейчас робот находится перед лестницу, ведущей на вершину горы. Лестница состоит из n ступенек. Робот, поднимаясь вверх, может пойти на одну или сразу две ступеньки.
Пока робот поднимается на вершину, вы хотите определить, сколько существует различных способов, которыми он может добраться до последней ступеньки этой лестницы и тем самым оказаться на вершине горы.
Входные данные
Программа получает на вход одно целое число n - количество ступенек в лестнице (1 <= n <= 45).
Выходные данные
Выведите одно число - количество способов добраться до вершины горы.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
2 |
2 |
| 2 |
3 |
3 |
Запрещенные операторы: for; while