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/kattisattachments/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.
Subtask 
Points 
Limits 
1 
9 
$1 \le N \le 100$ 
2 
11 
$1 \le N \le 5\, 000$ 
3 
14 
$1 \le N \le 100\, 000$. Each letter of $X$ was chosen randomly with uniform probability. 
4 
25 
$1 \le N \le 100\, 000$. $X$ is a Fibonacci string. 
5 
45 
$1 \le N \le 100\, 000$ 
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).
Sample Input 1  Sample Output 1 

6 abaaba 
12 