Перетворення#492
Розглянемо послідовність, що складається з одного біта "0". Далі виконаємо кроків наступним чином: на кожному кроці кожен біт "0" замінюємо на два біти "10", а кожен біт "1" — на два біти "01".
Після першого кроку послідовність "0" стає "10"; після другого — "0110"; після третього — "10010110"; після четвертого — "0110100110010110"; і так далі.
Напишіть програму, яка визначає кількість суміжних пар бітів "00" у послідовності після -го кроку.
У вхідних даних міститься єдине ціле число (1 \leq N \leq 1000).
Виведіть кількість суміжних пар "00" після -го кроку.
Приклад 1