Строки Фибоначчи
Medium
Execution time limit is 1 second
Runtime memory usage limit is 256 megabytes
Вам дана строка Фибоначчи f_k, нужно найти, сколько в ней подстрок палиндромов. Строка Фибоначчи определяется из следующего рекуррентного соотношения:
f_{0 }= a, f_{1 }= b, f_{n }= f_n_{-2}+f_n_{-1} (n > 1).
Первые пять строк Фибоначчи: "a", "b", "ab", "bab", "abbab".
Строка называется палиндромом, если она читается одинаково, как слева направо, так и справа налево. Например, строка "ded" — палиндром.
Input
В первой строке записано целое число k (0 ≤ k ≤ 30) — номер строки Фибоначчи.
Output
Выведите единственное целое число — сколько в строке f_{k }подстрок палиндромов.
Examples
Input #1
Answer #1
Submissions 93
Acceptance rate 14%