Problems
Строки Фибоначчи
Строки Фибоначчи
Вам дана строка Фибоначчи \textbf{f_k}, нужно найти, сколько в ней подстрок палиндромов. Строка Фибоначчи определяется из следующего рекуррентного соотношения:
\textbf{f_\{0 \}= a, f_\{1 \}= b, f_\{n \}= f_n_\{-2\}+f_n_\{-1\} (n} > \textbf{1)}.
Первые пять строк Фибоначчи: "\textbf{a}", "\textbf{b}", "\textbf{ab}", "\textbf{bab}", "\textbf{abbab}".
Строка называется палиндромом, если она читается одинаково, как слева направо, так и справа налево. Например, строка "\textbf{ded}" --- палиндром.
\InputFile
В первой строке записано целое число \textbf{k} (\textbf{0} ≤ \textbf{k} ≤ \textbf{30}) --- номер строки Фибоначчи.
\OutputFile
Выведите единственное целое число --- сколько в строке \textbf{f}_\{k \}подстрок палиндромов.
Input example #1
4
Output example #1
8