Задача E. Чередующиеся цифры ≡

Условие

Евгений разработал шифр для обмена сообщениями с друзьями. Пока шифр работает только для чисел по следующему алгоритму:

1) Заданное натуральное число разбивается на цифры.

2) Каждая цифра переводится в двоичную систему счисления.

3) Двоичные записи записываются подряд без пробелов.

Например, для числа 195 алгоритм сработает так: 195 - 1 9 5 - 1 1001 101 - 11001101.

Евгений зашифровал одно натуральное число и получил двоичную запись длины n, в которой единицы и нули чередуются. Эту запись он передал своему другу Артёму, а через несколько минут получил от него сообщение, в котором говорилось, что этот шифр никуда не годится, поскольку существует несколько чисел, которые будут зашифрованы одинаково. Более того, Артём точно указал количество таких чисел! Попробуйте написать программу, определяющую это количество.

Формат входных данных

Единственная строка входного файла содержит натуральное число n - длину двоичной записи чередующихся единиц и нулей.

Формат выходных данных

Выведите одно натуральное число - количество различных чисел, которые можно зашифровать такой записью. Гарантируется, что ответ не превысит 10¹⁸

Ограничения

1 ≤ n ≤ 90

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при 1 ≤ n ≤ 10, получат не менее 18 баллов.

Пояснение к примеру

В примере дано n = 3, значит двоичная запись имеет вид 101. Существует три числа, которые могут быть зашифрованы таким образом: 5, 21 и 101.

Примеры тестов

3

3