Максим написал супер-архиватор. Архивирует битовые маски длиной n, да такие, что никакие две единицы в них не стоят рядом. Вот только разорхивировать он их не может. Ответов может быть много.
Формат входных данных
Натуральное n (1 \leq n \leq 70) - длина маски.
Формат выходных данных
Количество битовых масок, в которых никакие две единицы не стоят рядом.
Примеры
| стандартный ввод | стандартный вывод |
|---|
| 1
| 2
|
| 2
| 3
|