Fibonacci Sıraları

Fibonacci sətirləri F(K) təbii ədədlər üçün aşağıdakı kimi müəyyən edilir: F(1) = "A", F(2) = "B", və K > 2 üçün F(K) = F(K - 1) + F(K - 2), burada "+" sətirlərin birləşdirilməsini göstərir. A və B simvollarından ibarət olan S sətirinin Fibonacci sətiri F(N) içində neçə dəfə təkrarlandığını tapmaq lazımdır.

Giriş verilənləri

Birinci sətirdə N ədədi, ikinci sətirdə isə S sətiri verilir. S sətirinin uzunluğu 1 ilə 25 arasında, 1 ≤ N ≤ 45, və F(45) sətirinin uzunluğu 1134903170 təşkil edir.

Çıxış verilənləri

Bir ədəd çıxarılır - S sətirinin Fibonacci sətiri F(N) içində neçə dəfə təkrarlandığı.

Nümunələr