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

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

1 секунда

256 мегабайтів

Середня

Вам задано рядок Фібоначчі $f_{k}$ \mathbf{f_k}. Знайдіть, скільки у ньому підрядків-паліндромів.

f_{0} = a, f_{1} = b, f_{n} = f_{n - 2} + f_{n - 1} (n > 1) .

\mathbf{f_0} = \text{a}, \quad \mathbf{f_1} = \text{b}, \quad \mathbf{f_n} = \mathbf{f_{n-2}} + \mathbf{f_{n-1}} \quad (n > 1).

Рядок Фібоначчі визначається наступним рекурентним співвідношенням:

Перші п'ять рядків Фібоначчі: "a", "b", "ab", "bab", "abbab".

Рядок називається паліндромом, якщо він читається однаково зліва направо і справа наліво. Наприклад, рядок "ded" — паліндром.

Вхідні дані

У першому рядку записано ціле число $k$ ( $0 \leq k \leq 30$ 0 \le k \le 30) — номер рядка Фібоначчі.

Виведіть єдине ціле число — скільки у рядку $f_{k}$ \mathbf{f_k} підрядків-паліндромів.

Приклад 1

Loading

f_{k}

f_{0} = a, f_{1} = b, f_{n} = f_{n - 2} + f_{n - 1} (n > 1) .

0 \leq k \leq 30

f_{k}