The Fibonacci word sequence of bit strings is defined as:

$$F(n)=\{\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}$$

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

0 & 0 
1 & 1
2 & 10
3 & 101
4 & 10110
5 & 10110101
6 & 1011010110110
7 & 101101011011010110101
8 & 1011010110110101101011011010110110
9 & 1011010110110101101011011010110110101101011011010110101

Given a bit pattern $p$ and a number $n$, how often does $p$ occur in $F(n)$?

INPUT 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 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}$.

SAMPLE INPUT

6
10
7
10

SAMPLE OUTPUT

Case 1: 5
Case 2: 8