Fibonacci Sözləri

Fibonacci söz ardıcıllığı bit sətirləri kimi aşağıdakı şəkildə müəyyən edilir:

Burada + işarəsi sətirlərin birləşdirilməsini ifadə edir. İlk bir neçə element belədir:

Verilən bit nümunəsi p və bir rəqəm n üçün, p nümunəsi F(n)-də neçə dəfə təkrarlanır?

Giriş verilənləri

Hər test halının ilk sətri tam ədəd n (0 ≤ n ≤ 100) ehtiva edir. İkinci sətir bit nümunəsi p-ni ehtiva edir. Nümunə p boş deyil və uzunluğu ən çox 100000 simvoldur.

Çıxış verilənləri

Hər test halı üçün, hal nömrəsini və F(n)-də bit nümunəsi p-nin təkrarlanma sayını göstərin. Təkrarlanmalar üst-üstə düşə bilər. Təkrarlanma sayı 2^63-dən az olacaq.

Nümunələr