Problem C
Fibonacci Strings

Aron likes Fibonacci numbers. He likes them so much he actually got bored of the numbers themselves and decided to invent other combinatorial objects based on them instead.

His first invention is the Fibonacci string. We call a string consisting of only letters $a$ and $b$, with exactly $n$ letters $a$ without any two consecutive letters $a$ a Fibonacci string of the $n$:th order.

Given a string $X$ of $a$:s and $b$:s, compute the sum of orders of all Fibonacci strings that are substrings of $X$. Note that if a string $X$ appears multiple times, its order should be counted once for every occurance.

Example

Assume that Aron has the string $abaaba$. This contains the Fibonacci string $a$ four times, $ab$ two times, $ba$ two times and $aba$ two times. The sum of their orders is $4 \cdot 1 + 2 \cdot 1 + 2 \cdot 1 + 2 \cdot 2 = 4 + 2 + 2 + 4 = 12$.

Task

Write a program that given $X$ computes the sum of orders of all Fibonacci substrings of $X$. You should implement the function fibonacci(N, X).

• fibonacci(N, X) - this function will be called exactly once by the judge.

  • N: an integer - the number of charaters in the string $X$.

  • X: a string consisting of $X$ characters, consisting only lowercase letters $a$ and $b$.

  • The function should return an integer, the sum of orders of all Fibonacci substrings of $X$.

A code skeleton containing the function to be implemented, together with a sample grader, can be found at http://progolymp.se/uploads/kattis-attachments/fibonacci.zip.

Subtasks

The problem consists of a number of subtasks. Each subtask gives some amount of points, and to pass the subtask you must pass all the test cases in the subtask.

Input format

The sample judge reads input in the following format:

• line $1$: N

• line $2$: X

Output format

The judge writes a single line containing the return value of fibonacci(N, X).

6
abaaba

12