The sequence of Fibonacci words is defined as follows: $Fib_{0} = b$, $Fib_{1} = a$, $Fib_{n} = Fib_{n-1}Fib_{n-2}$ for $n ≥ 2$. $Fib_{n}$ is the concatenation of $Fib_{n-1}$ and $Fib_{n-2}$.

The first few Fibonacci words are: b,a,ab,aba,abaab,abaababa,abaababaabaab,...

A word $u$ is a subword of a word $v$ if $v$ can be written as $v = xuy$ for some (possibly empty) words $x$ and $y$.

Write a program which:

• read a word $α$ (a sequence of letters a and b) and a sequence number $m$ of the Fibonacci word $Fib_m$;
• computes the number of times the word $α$ occurs in $Fib_m$ as a subword and the number of nonempty words that occur as a subword in $Fib_{m}$ at least as frequently as $α$.
• writes the answer to the standard output.

Input Format

The first line contains one integer $m$ ($0 ≤ m ≤ 1\,000\,000\,000$). We will examine the Fibonacci word $Fib_{m}$. The second line contains one word $α$ (a sequence of no more than $1\,000\,000$ and no less than one letter a and/or b).

Output Format

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 $Fib_{m}$ as a subword. The latter is the number of nonempty words which occur in $Fib_m$ as subwords at least as frequently as $α$ occurs in $Fib_{m}$.

Both numbers should be written modulo 20062006 (you should write the remainder of the division of these numbers by 20062006).

You can assume, that the word $α$ is a subword of the given Fibonacci word.

Example

Input

5
aba

Output

3 5

Notes

The subwords of $Fib_{5}$ which occur in $Fib_{5}$ at least as frequently as aba are: a, b, ab, baand aba.