Задача №111727. Road
Найти количество покрытий прямоугольника 2 * n фигурами в виде дощечек, каждая из которых представляет собой либо квадрат со стороной 1, либо два квадрата (2 * 1), либо “уголок” из трех квадратов:
Фигуры должны заполнять прямоугольник без промежутков.
Входные данные
Вводится число n(1 ≤ n ≤ 1000).
Выходные данные
Выведите количество возможных покрытий.
Примеры
Входные данные
2
Выходные данные
11
Сдать: для сдачи задач необходимо войти в систему