Строки Фибоначчи

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

Примеры