Xâu Fibonacci

Xét dãy các xâu F1, F2, F3, ..., FN, ... trong đó:
F1 = 'A'
F2 = 'B'
FK+1 = FK + FK-1 (K  2).
Ví dụ:
     F1 = 'A'
     F2 = 'B'
     F3 = 'BA'
     F4 = 'BAB'
     F5 = 'BABBA'
     F6 = 'BABBABAB'
     F7 = 'BABBABABBABBA'
     F8 = 'BABBABABBABBABABBABAB'
     F9 = 'BABBABABBABBABABBABABBABBABABBABBA'
Cho xâu S độ dài không quá 25, chỉ bao gồm các ký tự 'A' và 'B'. Hãy xác định số lần xuất hiện xâu S trong xâu FN, N<=35. Chú ý: hai lần xuất hiện của S trong FN không nhất thiết phải là các xâu rời nhau hoàn toàn.
Dữ liệu: vào từ file văn bản FIBISTR.INP, bao gồm nhiều dòng, mỗi dòng có dạng N S. Giữa N và S có đúng 1 dấu cách. Dữ liệu vào là chuẩn, không cần kiểm tra.
Kết quả: Đưa ra file văn bản FIBISTR.OUT, mỗi dòng dữ liệu ứng với một dòng kết quả

Ví dụ:
     FIBISTR.INP              FIBISTR.OUT
            3 A                                1
            3 AB                              0
            8 BABBAB                    4
                                                           Lời giải tham khảo