The sequence of Fibonacci words is defined as follows:
,
,
.
is the concatenation of
and
.
The first few Fibonacci words are: b,a,ab,aba,abaab,abaababa,abaababaabaab,...
A word
is a subword of a word
if
can be written as
for some (possibly empty) words
and
.
Write a program which:
(a sequence of letters a and b)
and a sequence number
of the Fibonacci word
;
occurs in
as a subword
and the number of nonempty words that occur as a subword in
at least as frequently as
.
The first line contains one integer
(
). We will examine the Fibonacci word
.
The second line contains one word
(a sequence of no more than
and no less than one letter a and/or b).
In the first and only line your program should write two numbers separated by a single
space. The former is the number of times the word
occurs in
as a subword.
The latter is the number of nonempty words which occur in
as subwords at least as frequently as
occurs in
.
Both numbers should be written modulo
(you should write the remainder of the division of these numbers by
).
You can assume, that the word
is a subword of
the given Fibonacci word.
For the input data:
5 aba
the correct result is:
3 5
The subwords of
which occur in
at least as frequently as aba are: a, b, ab, ba and aba.
Task author: Jakub Radoszewski.
W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem szkopul@fri.edu.pl.
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, odwiedź nasze serwery na Discordzie. Są one moderowane przez społeczność, ale członkowie zespołu wsparcia również aktywnie się tam udzielają.