Рядки Фібоначчі

Рядки Фібоначчі F(K) для натуральних чисел K визначимо так: F(1) = "A", F(2) = "B", F(K) = F(K - 1) + F(K - 2) при K > 2, де "+" означає конкатенацію рядків. Потрібно знайти кількість входжеь рядка S, який складається з символів A та B, у рядок Фібоначчі F(N).

Вхідні дані

У першому рядку міститься число N, у другому - рядок S. Довжина S від 1 до 25, 1 ≤ N ≤ 45, довжина F(45) становить 1134903170.

Вихідні дані

Виводиться одне число - кількість входжень рядка S у рядок Фібоначчі F(N).

Приклади