Fibonacci Words

Fibonacci words are defined in a way similar to Fibonacci numbers:

$\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)$

where $\oplus$ denotes concatenation of two words.

The first few Fibonacci words are therefore $\mathrm{FIB}_3 = \texttt{ab}$, $\mathrm{FIB}_4 = \texttt{aba}$, $\mathrm{FIB}_5 = \texttt{abaab}$, $\mathrm{FIB}_6 = \texttt{abaababa}$.

You are given a pattern word made only of the letters a and b, together with an integer $n$. Count how many times the pattern appears as a contiguous fragment of the $n$-th Fibonacci word $\mathrm{FIB}_n$. Two occurrences may overlap, so every starting position whose fragment equals the pattern is counted separately.

The first line contains the pattern word. It consists of between $1$ and $30$ characters, each of which is a or b.

The second line contains one positive integer $n$ with $n \le 200$.

Print one nonnegative integer: the number of times the pattern word appears in $\mathrm{FIB}_n$. The answer can be very large and may not fit in a 64-bit integer.