Строку Фибоначчи F(K) для натуральных чисел K определим так: F(1) = 'A', F(2) = 'B', F(K) = F(K - 1) + F(K - 2) при K > 2, где "+" означает конкатенацию строк. Требуется найти количество вхождений строки S, состоящей из символов A и B, в строку Фибоначчи F(N).
Ограничения: длина S от 1 до 25, 1 <= N <= 45.
Примечание. Длина F(45) равна 1 134 903 170.
Входные данные
В первой строке содержится число N, во второй - строка S.
Выходные данные
Выводится одно число - количество вхождений строки S в строку Фибоначчи F(N).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
A
|
1
|
|
2
|
1
B
|
0
|
|
3
|
1
BBABBABABBABABBABBABABBAB
|
0
|