Fibostrings

Fibonacci string F(K) for K positive integers defined as follows: F(1) = "A", F(2) = "B", F(K) = F(K - 1) + F(K - 2) for K > 2, where "+" denotes string concatenation. Required to find the number of occurrences of a string S, consisting of the characters A and B, in the Fibonacci string F(N).

Input

The first line contains the number N, the second - a string S. The length of S from 1 to 25, 1 ≤ N ≤ 45, the length of F(45) is equal to 1,134,903,170.

Output

We derive a single number - the number of occurrences of a string S in the Fibonacci string F(N).

Examples