Southeastern European Regional Programming Contest  Bucharest, Romania  October 23, 1999

Problem B
Fibonacci Strings

Source File: fibstring.cc

A Fibonacci string F(n) for a natural number n is defined as follows:

F(1) = "A"
F(2) = "B"
F(n) = F(n-1) + F(n-2),  for n>2,

where + denotes string concatenation.

Write a program that counts occurrences of a given string S (which will consisti of the characters A and B only) in the given Fibonacci string F(n). The maximum length of S is 25, the maximum value of the given n is 35, and the result might have up to 8 digits.

The input file contains a sequence of input data sets. Each data set is given in one line, consisting of an integer n and a string S. The input should be read from the file. The input is guaranteed to be correct.

The output should be printed on the standard output. For each given input data set, print one integer number in a single line that gives the result (the number of occurrences of S in F(n)).

Example input file

1 A
2 ABA
6 AB
8 BBABAB

Example output file

1
0
3
3