Задача C. Суперфакториальная система счисления

Задача D. Мини-Тетрис 2.0
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Имеются прямоугольные плитки двух типов — одноклеточные квадраты размером 1 × 1 и двухклеточные прямоугольники размером 1 × 2. С помощью этих плиток необходимо замостить полосу
размером 2×n, при этом плитки не должны накладываться друг на друга и каждая клетка полосы
должна быть покрыта ровно одной плиткой. Плитки разрешается поворачивать.
Вам необходимо подсчитать количество способов замощения полосы 2 × n с помощью плиток
указанного вида.
Формат входных данных
Во входных данных записано одно целое число n — длина полосы (1 6 n 6 1018).
Формат выходных данных
Выведите количество способов замощения полосы с помощью плиток указанного вида. Ответ
запишите по модулю (109 + 9).