Fibonacci Words#3390
The Fibonacci word sequence of bit strings is defined as:
Here + denotes concatenation of strings. The first few elements are:
Given a bit pattern and a number , how often does occur in ?
The first line of each test case contains the integer (0 \le n \le 100). The second line contains the bit pattern . The pattern is nonempty and has a length of at most characters.
For each test case, display its case number followed by the number of occurrences of the bit pattern in . Occurrences may overlap. The number of occurrences will be less than 2^{63}.
Example 1