피보나치 단어

피보나치 단어는 피보나치 수와 비슷한 방식으로 정의된다.

$\mathrm{FIB}_1 = \texttt{b}, \quad \mathrm{FIB}_2 = \texttt{a}, \quad \mathrm{FIB}_{k+2} = \mathrm{FIB}_{k+1} \oplus \mathrm{FIB}_k \quad (k \ge 1)$

여기서 $\oplus$는 두 단어를 이어 붙이는 연산(연결, concatenation)을 뜻한다.

따라서 처음 몇 개의 피보나치 단어는 $\mathrm{FIB}_3 = \texttt{ab}$, $\mathrm{FIB}_4 = \texttt{aba}$, $\mathrm{FIB}_5 = \texttt{abaab}$, $\mathrm{FIB}_6 = \texttt{abaababa}$ 이다.

문자 a와 b로만 이루어진 패턴 단어와 정수 $n$이 주어진다. 이 패턴이 $n$번째 피보나치 단어 $\mathrm{FIB}_n$ 안에서 연속한 부분 문자열로 몇 번 나타나는지 세어라. 두 등장은 서로 겹칠 수 있으므로, 패턴과 일치하는 모든 시작 위치를 각각 하나로 센다.

첫째 줄에 패턴 단어가 주어진다. 이 단어는 a 또는 b로 이루어져 있으며 길이는 $1$ 이상 $30$ 이하이다.

둘째 줄에 양의 정수 $n$이 주어진다. ($n \le 200$)

패턴 단어가 $\mathrm{FIB}_n$ 안에 나타나는 횟수를 음이 아닌 정수 하나로 출력한다. 답은 매우 클 수 있으며 64비트 정수 범위를 넘을 수 있다.