URI Online Judge | 2208
# Fibonacci Words

**Timelimit: 5**

By ICPC 2012 World Finals Poland

The Fibonacci word sequence of bit strings is defined as:

$$F(n) =\begin{cases} & \text 0 \\ & \text 1 \\ & \text F(n-1)+F(n-2)\\ \end{cases} \begin{matrix} \mathbf{if} n = 0 \\ \mathbf{if} n = 1\\ \mathbf{if} n \geqslant 2 \end{matrix}$$Here + denotes concatenation of strings. The first few elements are:

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 ≤ **n** ≤ 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} .

Input Sample | Output Sample |

6 10 7 10 6 01 6 101 96 10110101101101 |
Case 1: 5 Case 2: 8 Case 3: 4 Case 4: 4 Case 5: 7540113804746346428 |