The Fibonacci word sequence of bit strings is defined as:
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 100000 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.