Fibonacci Words

Memory limit: 64 MB

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 .

Task

Write a program which:

• reads a word (a sequence of letters a and b) and a sequence number of the Fibonacci word ;
• computes the number of times the word occurs in as a subword and the number of nonempty words that occur as a subword in at least as frequently as .
• writes the answer to the standard output.

Input

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).

Output

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.

Example

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.