Fibonacci string \textbf{F}(\textbf{K}) for \textbf{K} positive integers defined as follows: \textbf{F}(\textbf{1}) = "\textbf{A}", \textbf{F}(\textbf{2}) = "\textbf{B}", \textbf{F}(\textbf{K}) = \textbf{F}(\textbf{K} - \textbf{1}) + \textbf{F}(\textbf{K} - \textbf{2}) for \textbf{K} > \textbf{2}, where "\textbf{+}" denotes string concatenation. Required to find the number of occurrences of a string \textbf{S}, consisting of the characters \textbf{A} and \textbf{B}, in the Fibonacci string \textbf{F}(\textbf{N}). \InputFile The first line contains the number \textbf{N}, the second - a string \textbf{S}. The length of \textbf{S} from \textbf{1} to \textbf{25}, \textbf{1} ≤ \textbf{N} ≤ \textbf{45}, the length of \textbf{F}(\textbf{45}) is equal to \textbf{1,134,903,170}. \OutputFile We derive a single number - the number of occurrences of a string \textbf{S} in the Fibonacci string \textbf{F}(\textbf{N}).