Słowa Fibonacciego

Limit pamięci: 32 MB

Słowa Fibonacciego definiujemy podobnie jak liczby Fibonacciego:

,

gdzie jest znakiem operacji łączenia (konkatenacji) słów.

Mamy zatem: , , , .

Zadanie

Napisz program, który:

• wczytuje ze standardowego wejścia słowo złożone z co najmniej jednej i co najwyżej liter lub oraz liczbę całkowitą dodatnią (),
• oblicza, ile razy dane słowo występuje w -tym słowie Fibonacciego (poszczególne wystąpienia danego słowa mogą częściowo na siebie zachodzić),
• zapisuje wynik na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia jest zapisane jedno słowo złożone z co najmniej jednej i co najwyżej małych liter lub . W drugim wierszu jest zapisana jedna liczba całkowita dodatnia .

Wyjście

W pierwszym i jedynym wierszu standardowego wyjścia należy zapisać jedną liczbę całkowitą nieujemną, która jest liczbą wystąpień danego słowa w -tym słowie Fibonacciego .

Przykład

Dla danych wejściowych:

aba
6

poprawną odpowiedzią jest:

3

Autor zadania: Wojciech Rytter.