Рядки Фібоначчі

Вам задано рядок Фібоначчі 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 }підрядків паліндромів.

Приклади