Рядки Фібоначчі \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}).