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