피보나치 단어

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

• $F_0 = \texttt{b}$
• $F_1 = \texttt{a}$
• $n \ge 2$일 때 $F_n = F_{n-1}F_{n-2}$ (오른쪽 항은 문자열 $F_{n-1}$과 $F_{n-2}$를 이어 붙인 것이다)

따라서 수열의 앞부분은 b, a, ab, aba, abaab, abaababa, abaababaabaab, ... 이다.

문자열 $u$가 문자열 $v$의 부분 단어(연속된 부분 문자열)라는 것은, 어떤 문자열 $x$, $y$에 대해 $v = x\,u\,y$로 쓸 수 있다는 뜻이다. ($x$, $y$는 빈 문자열이어도 된다.)

a와 b로만 이루어진 문자열 $\alpha$와 정수 $m$이 주어진다. 피보나치 단어 $F_m$ 안에 $\alpha$가 부분 단어로 몇 번 나타나는지 세고(겹쳐서 나타나는 경우도 각각 센다), 또한 $F_m$의 비어 있지 않은 서로 다른 부분 단어 중에서 $F_m$ 안에서의 등장 횟수가 $\alpha$의 등장 횟수 이상인 것이 몇 개인지 구하여라.

첫째 줄에 정수 $m$ ($0 \le m \le 1{,}000{,}000{,}000$)이 주어진다.

둘째 줄에 문자열 $\alpha$가 주어진다. $\alpha$는 a와 b로만 이루어져 있고 길이는 $1{,}000{,}000$ 이하이며, 항상 $F_m$의 부분 단어이다.

두 정수를 공백으로 구분하여 한 줄에 출력한다.

• 첫 번째 정수: $F_m$ 안에 $\alpha$가 부분 단어로 나타나는 총 횟수.
• 두 번째 정수: $F_m$의 비어 있지 않은 서로 다른 부분 단어 중에서, $F_m$ 안에서의 등장 횟수가 $\alpha$의 등장 횟수 이상인 것의 개수.

두 수 모두 매우 커질 수 있으므로 $20062006$으로 나눈 나머지를 출력한다.

$F_5$는 abaababa이고, 이 안에서 aba는 3번 나타난다. $F_5$의 비어 있지 않은 서로 다른 부분 단어 중에서 3번 이상 나타나는 것은 a, b, ab, ba, aba의 5개이다.