Строки Фибоначчи

Строку Фибоначчи 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).

Примеры