피보나치 단어의 수열은 다음과 같이 정의한다.

Fib₀ = b, Fib₁ = a, Fib_n = Fib_n-1Fib_n-2 (n ≥ 2)

Fib_n은 Fib_n-1과 Fib_n-2를 이어 붙인 것이다.

피보나치 단어 수열의 첫 부분은 b,a,ab,aba,abaab,abaababa,abaababaabaab,... 이다.

단어 u가 단어 v의 부분 단어가 되려면, 임의의 단어 x와 y에 대해서 v = xuy로 쓸 수 있어야 한다. (x와 y는 빈 단어일 수도 있다)

a와 b로만 이루어진 단어 α와 피보나치 단어 Fib_m을 나타내는 m이 주어진다. 이때, Fib_m에 α가 부분 단어로 몇 번 등장하는지 구하고, Fib_m의 부분 단어 중에서 α가 적어도 등장하는 횟수만큼 등장하는 비어있지 않은 부분 단어의 개수를 구하는 프로그램을 작성하시오.

입력 형식

첫째 줄에 m (0 ≤ m ≤ 1,000,000,000)이 주어진다. 둘째 줄에는 단어 α가 주어진다. α는 a와 b로만 이루어져 있으며, 길이는 1,000,000을 넘지 않는다.

출력 형식

첫째 줄에 두 숫자를 출력한다. 첫 번째 숫자는 Fib_m에 α가 부분 단어로 총 몇 번 등장하는지를 나타내는 숫자이다. 두 번째 단어는 Fib_m의 모든 부분 단어 중에서, 적어도 α가 등장하는 만큼 등장하는 비어있지 않은 부분 단어의 개수를 출력한다.

두 숫자는 매우 클 수 있기 때문에 20062006으로 나눈 나머지를 출력한다. 

입력으로 주어지는 α는 항상 주어진 피보나치 단어의 부분 단어이다.

예제 입력

5
aba

예제 출력

3 5

힌트

Fib₅에서 적어도 aba가 등장하는 만큼 등장하는 비어있지 않은 부분 단어는 a, b, ab, ba, aba이다.