Вам задано рядок Фібоначчі f_k, потрібно знайти, скільки у ньому підрядків паліндромів. Рядок Фібоначчі визначається з наступного рекурентного співвідношення:
f_{0 }= a, f_{1 }= b, f_{n }= f_n_{-2}+f_n_{-1} (n > 1).
Перші п'ять рядків Фібоначчі: "a", "b", "ab", "bab", "abbab".
Рядок називається паліндромом, якщо він читається однаково, як зліва направо, так і зправа наліво. Наприклад, рядок "ded" — паліндром.
У першому рядку записано ціле число k (0 ≤ k ≤ 30) — номер рядка Фібоначчі.
Виведіть єдине ціле число — скільки у рядку f_{k }підрядків паліндромів.