시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 2 1 1 50.000%

문제

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

Fib0 = b, Fib1 = a, Fibn = Fibn-1Fibn-2 (n ≥ 2)

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

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

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

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

입력

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

출력

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

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

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

예제 입력

5
aba

예제 출력

3 5

힌트

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

출처

Contest > Algorithmic Engagements > PA 2006 14번