Fibonacci Strings

Time limit1sMemory limit1024 MB

Summary

Sum the orders (counts of letter a) of every substring of X that is a Fibonacci string, meaning it has no two adjacent a's, counting each occurrence separately.

Level: Hard8 of 10
Topics: String, Dynamic programming, Combinatorics, Prefix sum
Solved: No attempts yet

Problem

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

His first invention is the Fibonacci string. A string consisting only of the letters $a$ and $b$ , with exactly $n$ letters $a$ and no two consecutive letters $a$ , is called a Fibonacci string of order $n$ .

Given a string $X$ of $a$ s and $b$ s, compute the sum of the orders of all Fibonacci strings that occur as substrings of $X$ . If a string occurs multiple times in $X$ , its order is counted once for each occurrence.

Input

The judge reads input in the following format:

line $1$ : N
line $2$ : X

Output

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

Constraints

$1 \le N \le 100\,000$

Examples1

Example 1
Input
```
6
abaaba
```
Expected output
```
12
```