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