ЛОШ2014: 20 июня 2014. Пройди на Всерос за 9 класс

Алла очень любит палиндромы. Все потому, что её имя является палиндромом. Напомним, что строку называют палиндромом тогда, когда она одинаково читается как слева направо, так и справа налево.

Однажды в школе учитель рассказал Алле про так называемые строки Фибоначчи. Строки Фибоначчи определяются следующим образом:

• f ₀ = a
• f ₁ = b
• f _n = f _{n −1} f _{n −2} для каждого n ≥ 2 — конкатенация двух предыдущих строк Фибоначчи

Таким образом, первые пять строк Фибоначчи: « a » , « b » , « ba » , « bab » , « babba » .

Аллу сразу заинтересовал вопрос — какой максимально длинный палиндром встречается в k -й строке Фибоначчи. Помогите Алле решить эту задачу.