시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 1024 MB 3 2 2 66.667%

## 문제

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.

## 예제

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$.

## 구현

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 attachments.zip.

## 입력

The sample judge reads input in the following format:

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

## 출력

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

## 제한

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

## 예제 입력 1

6
abaaba


## 예제 출력 1

12


## 출처

• 문제를 만든 사람: Johan Sannemo

## 제출할 수 있는 언어

C++17, Java 8, C++14, Java 8 (OpenJDK), Java 11, C++20, Java 15, C++14 (Clang), C++17 (Clang), C++20 (Clang)

## 채점 및 기타 정보

• 예제는 채점하지 않는다.