Строку Фибоначчи \textbf{F}(\textbf{K}) для натуральных чисел \textbf{K} определим так: \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}) при \textbf{K} > \textbf{2}, где "\textbf{+}" означает конкатенацию строк. Требуется найти количество вхождений строки \textbf{S}, состоящей из символов \textbf{A} и \textbf{B}, в строку Фибоначчи \textbf{F}(\textbf{N}). \InputFile В первой строке содержится число \textbf{N}, во второй - строка \textbf{S}. Длина \textbf{S} от \textbf{1} до \textbf{25}, \textbf{1} ≤ \textbf{N} ≤ \textbf{45}, длина \textbf{F}(\textbf{45}) равна \textbf{1134903170}. \OutputFile Выводится одно число - количество вхождений строки \textbf{S} в строку Фибоначчи \textbf{F}(\textbf{N}).