Задача E. Дорожка из плиток ≡
| Автор: | Антон Карабанов | Ограничение времени: | 1 сек | |
| Входной файл: | Стандартный вход | Ограничение памяти: | 256 Мб | |
| Выходной файл: | Стандартный выход |
Условие
чтобы, не дай Бог, в стык между плитками не попала дамская шпилька, а то крику будет...
Тимофею необходимо уложить на узкой парковой дорожке размером 6 × n тротуарную плитку. У него есть неограниченное количество плиток двух типов: 2 × 2 и 3 × 3. Сколько существует различных способов заполнения дорожки? Заказчик требует качественной работы, поэтому плитки нельзя ломать, каждая плитка должна плотно прилегать к соседней без наложений, дорожка должна быть заполнена полностью, края плитки не могут выходить за пределы дорожки.
Формат входных данных
Единственная строка входных данных содержит натуральное число n.
Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64-битный тип данных, например long long в C++, int64 в Free Pascal, long в Java.
Формат выходных данных
Выведите одно натуральное число — ответ на вопрос задачи.
Ограничения
2 ≤ n ≤ 150
Пояснение к примеру
В примере дано n = 5. Смотри рисунок.
Примеры тестов
| № | Стандартный вход | Стандартный выход |
|---|---|---|
| 1 | |
|