Рядки Фібоначчі#870
Фібоначчієві рядки для додатних цілих чисел визначаються так: F(1)=\text{``A''}, F(2)=\text{``B''}, а для K>2 — F(K)=F(K-1)+F(K-2), де "" означає конкатенацію рядків. Потрібно знайти кількість входжень рядка , що складається з символів та , у Фібоначчієвому рядку .
У першому рядку задано ціле число , у другому — рядок . Довжина від до , 1 \leq N \leq 45, а довжина дорівнює .
Виведіть одне ціле число — кількість входжень рядка у Фібоначчієвому рядку .
Приклад 1