Задача E. 2-3 числа ≡

Условие

Будем называть 2-3 числом такое натуральное число, у которого все соседние цифры отличаются друг от друга либо в 2, либо в 3 раза. Определите количество 2-3 чисел длины n.

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

Единственная строка входных данных содержит натуральное число n.

Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64-битный тип данных, например long long в C++, int64 в Free Pascal, long в Java.

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

Выведите одно натуральное число — ответ на вопрос задачи.

Ограничения

2 ≤ n ≤ 48

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

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

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

В примере дано n = 2. Перечислим все двузначные 2-3 числа: 12, 13, 21, 24, 26, 31, 36, 39, 42, 48, 62, 63, 84, 93. Всего 14 чисел.

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

2

14