Fibonacci Words

Description

The Fibonacci word sequence of bit strings is defined as:

$$F(n) = \left\{ \begin{array}{ll} 0 & \text {if $n = 0$}\\ 1 & \text {if $n = 1$}\\ F(n-1) + F(n-2) & \text {if $n \ge 2$} \end{array}\right.$$

Here $+$ denotes concatenation of strings. The first few elements are:

Input format

The first line of each test case contains the integer $n$ ($0 \le n \le 100$). The second line contains the bit pattern $p$. The pattern $p$ is nonempty and has a length of at most $100\, 000$ characters.

Output format

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 $\mathrm{2}^\mathrm {63}$.

Input Sample 1

6
10
7
10
6
01
6
101
96
10110101101101

Output Sample 1

Case 1: 5
Case 2: 8
Case 3: 4
Case 4: 4
Case 5: 7540113804746346428