0.SE. Fibonacci Words

Submit solution
Points: 4 (partial)
Time limit: 1.0s
Memory limit: 98M
Author:
nguyennghia_nh
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

The Fibonacci word sequence of bit strings is de?ned as:

F(n) = 0 if n = 0 1 if n = 1 F(n-1) + F(n+2) if n >= 2

Here denotes concatenation of strings. The ?rst few elements are:

n F(n)

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 ?rst 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.

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 263.

Examples

Input

6

10

Output

Case 1: 5