printРайонно-городское личное первенство

print3. Преобразования

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0) idea

Возьмем последовательность из одного бита "0". Далее выполняем `N` следующих шагов. На каждом шаге бит "0" заменяем на два бита "10", а бит "1" на два бита "01". После выполнения первого шага из последовательности "0" получается последовательность "10", после второго – "0110", после третьего – "10010110", после четвертого – "0110100110010110", и так далее.
Напишите программу, которая определяет количество соседних битов "00" в последовательности после `N`-го шага.
Вводится одно целое число `N` (`1\ ≤\ N\ ≤\ 1000`).
Вывести количество соседей "00" после `N`-го шага.

Пример ввода

4

Пример вывода

2
loading