Fibonacci Strings#5909
Sign in

Fibonacci Strings

1 second
256 megabytes
Medium

You are given the Fibonacci string \mathbf{f_k}. Find how many of its substrings are palindromes.

The Fibonacci string is defined by the following recurrence relation:

\mathbf{f_0} = \text{a}, \quad \mathbf{f_1} = \text{b}, \quad \mathbf{f_n} = \mathbf{f_{n-2}} + \mathbf{f_{n-1}} \quad (n > 1).

The first five Fibonacci strings are: "a", "b", "ab", "bab", "abbab".

A string is called a palindrome if it reads the same left-to-right and right-to-left. For example, the string "ded" is a palindrome.

Input

The first line contains an integer (0 \le k \le 30) — the index of the Fibonacci string.

Output

Print a single integer — the number of palindromic substrings in the string \mathbf{f_k}.

Examples

Example 1

Loading
Loading