Time Limit: 1s
Memory Limit: 256MB
The Fibonacci word sequence of bit strings is defined as:
\[ F(n) =
\begin{cases}
0 & \quad \text{if } n =0\\
1 & \quad \text{if } n=1\\
F(n-1)+F(n-2) & \quad \text{if } n\geq 2\\
\end{cases}
\]
Here denotes concatenation of strings. The first few elements are:
\begin{table}[h]
\centering
\begin{tabular}{|c|c|}
\hline
n & F(n) \\
\hline
0 & 0 \\
1 & 1\\
2 & 10\\
3 & 101\\
4 & 10110\\
5 & 10110101\\
6 & 1011010110110\\
7 & 101101011011010110101\\
8 & 1011010110110101101011011010110110\\
9 & 1011010110110101101011011010110110101101011011010110101\\
\hline
\end{tabular}
\end{table}
Given a bit pattern $p$ and a number $n$, how often does $p$ occur in $F(n)$?
The first line of each test case contains the integer $n$ ($0 \leq n \leq 100$). The second line contains the bit pattern $p$. The pattern $p$ is nonempty and has a length of at most 100 000 characters.
For each test case, display its case number followed by the number of occurrences of the bit pattern $p$ in $F(n)$. Occurrences may overlap. The number of occurrences will be less than $2^{63}$.
6 10 7 10
Case 1: 5 Case 2: 8