Słowa Fibonacciego

Limit pamięci: 64 MB

Ciąg słów Fibonacciego definiujemy następująco: , , . W powyższym zapisie określamy jako sklejenie słów i .

Kilka kolejnych słów Fibonacciego to: b,a,ab,aba,abaab,abaababa,abaababaabaab,...

Słowo jest podsłowem slowa , jeżeli słowo możemy zapisać jako , gdzie i są pewnymi (być może pustymi) słowami.

Zadanie

Napisz program który:

• wczyta ze standardowego wejścia jedno słowo złożone z liter a i b i numer słowa Fibonacciego,
• wyznaczy liczbę wystąpień wczytanego słowa jako podsłowa w danym słowie Fibonacciego, a także liczbę słów, których liczba wystąpień jako podsłów w tym słowie Fibonacciego jest nie mniejsza od tej liczby,
• wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu znajduje się jedna liczba całkowita (), oznaczająca numer słowa Fibonacciego. W drugim wierszu wejścia znajduje się jedno słowo, które składa się z nie więcej niż , oraz nie mniej niż jednej litery a lub b.

Wyjście

W pierwszym i jedynym wierszu należy wypisać dwie liczby całkowite oznaczające resztę z dzielenia przez liczby wystąpień wczytanego słowa jako podsłowa danego słowa Fibonacciego oraz resztę z dzielenia przez liczby niepustych słów (złożonych z liter a i b), których liczba wystąpień jako podsłów danego słowa Fibonacciego jest nie mniejsza od liczby wystąpień wczytanego słowa (dane słowo wlicza się oczywiście do tych podsłów).

Możesz założyć, że podane na wejściu słowo jest podsłowem danego na wejściu słowa Fibonacciego.

Przykład

Dla danych wejściowych:

5
aba

poprawną odpowiedzią jest:

3 5

Podsłowami słowa spełniającymi warunki zadania są: a, b, ab, ba i wreszcie aba.

Autor zadania: Jakub Radoszewski.