Читая старый учебник по алгебре, профессор Р. наткнулся на интересные числовые последовательности, называемые последовательностями Грея. Первая последовательность Грея состоит из числа $$$1$$$, вторая последовательность Грея состоит из чисел $$$1, 2, 1$$$, третья последовательность Грея равна $$$1, 2, 1, 3, 1, 2, 1$$$ и т. д., последовательность Грея с номером $$$i$$$ состоит из $$$(i - 1)$$$-й последовательности Грея, числа $$$i$$$ и вновь записанной $$$(i - 1)$$$-й последовательности Грея. Профессор обозначил через $$$f(n)$$$ сумму чисел в $$$n$$$-й последовательности Грея и просит вас написать программу, которая найдёт правильный ответ для заданного $$$n$$$. Так как эта сумма может оказаться очень большой, он просит посчитать остаток от деления суммы на число $$$10^9 + 9$$$.