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