Fibostrings#870
Fibonacci strings for positive integers are defined as follows: F(1)=\text{``A''}, F(2)=\text{``B''}, and for K>2, F(K)=F(K-1)+F(K-2), where "" denotes string concatenation. You are required to find the number of occurrences of a string , consisting of the characters and , in the Fibonacci string .
The first line contains the integer , and the second line contains the string . The length of is from to , 1 \leq N \leq 45, and the length of is .
Output a single integer — the number of occurrences of the string in the Fibonacci string .
Example 1