The Fibonacci word sequence of bit strings is defined as: \includegraphics{https://static.e-olymp.com/content/0f/0fb0f06d86bb723e55d7e8b9707b9de9e20dc834.jpg} Here + denotes concatenation of strings. The first few elements are: Given a bit pattern \textbf{p} and a number \textbf{n}, how often does \textbf{p} occur in \textbf{F(n)}? \InputFile The first line of each test case contains the integer \textbf{n} (\textbf{0} ≤ \textbf{n} ≤ \textbf{100}). The second line contains the bit pattern \textbf{p}. The pattern \textbf{p} is nonempty and has a length of at most \textbf{100000} characters. \OutputFile For each test case, display its case number followed by the number of occurrences of the bit pattern \textbf{p} in \textbf{F(n)}. Occurrences may overlap. The number of occurrences will be less than \textbf{2^63}.