시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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으로 나눈 나머지를 출력한다. 

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

예제 입력 1

5
aba

예제 출력 1

3 5

힌트

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

W3sicHJvYmxlbV9pZCI6Ijg0MDYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTggXHViMmU4XHVjNWI0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTggXHViMmU4XHVjNWI0XHVjNzU4IFx1YzIxOFx1YzVmNFx1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YzgxNVx1Yzc1OFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+RmliPHN1Yj4wPFwvc3ViPiA9IGIsIEZpYjxzdWI+MTxcL3N1Yj4gPSBhLCBGaWI8c3ViPm48XC9zdWI+ID0gRmliPHN1Yj5uLTE8XC9zdWI+RmliPHN1Yj5uLTI8XC9zdWI+IChuICZnZTsgMik8XC9wPlxyXG5cclxuPHA+RmliPHN1Yj5uPFwvc3ViPlx1Yzc0MCBGaWI8c3ViPm4tMTxcL3N1Yj5cdWFjZmMgRmliPHN1Yj5uLTI8XC9zdWI+XHViOTdjIFx1Yzc3NFx1YzViNCBcdWJkOTlcdWM3NzggXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTggXHViMmU4XHVjNWI0IFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWNjYWIgXHViZDgwXHViZDg0XHVjNzQwIGIsYSxhYixhYmEsYWJhYWIsYWJhYWJhYmEsYWJhYWJhYmFhYmFhYiwuLi4gXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZThcdWM1YjQgdVx1YWMwMCBcdWIyZThcdWM1YjQgdlx1Yzc1OCBcdWJkODBcdWJkODQgXHViMmU4XHVjNWI0XHVhYzAwIFx1YjQxOFx1YjgyNFx1YmE3NCwgXHVjNzg0XHVjNzU4XHVjNzU4IFx1YjJlOFx1YzViNCB4XHVjNjQwIHlcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIHYgPSB4dXlcdWI4NWMgXHVjNGY4IFx1YzIxOCBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiAoeFx1YzY0MCB5XHViMjk0IFx1YmU0OCBcdWIyZThcdWM1YjRcdWM3N2MgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNCk8XC9wPlxyXG5cclxuPHA+YVx1YzY0MCBiXHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWIyZThcdWM1YjQgJmFscGhhO1x1YzY0MCBcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTggXHViMmU4XHVjNWI0IEZpYjxzdWI+bTxcL3N1Yj5cdWM3NDQgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IG1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWI1NGMsIEZpYjxzdWI+bTxcL3N1Yj5cdWM1ZDAgJmFscGhhO1x1YWMwMCBcdWJkODBcdWJkODQgXHViMmU4XHVjNWI0XHViODVjIFx1YmE4NyBcdWJjODggXHViNGYxXHVjN2E1XHVkNTU4XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YWNlMCwgRmliPHN1Yj5tPFwvc3ViPlx1Yzc1OCBcdWJkODBcdWJkODQgXHViMmU4XHVjNWI0IFx1YzkxMVx1YzVkMFx1YzExYyZuYnNwOyZhbHBoYTtcdWFjMDAgXHVjODAxXHVjNWI0XHViM2M0IFx1YjRmMVx1YzdhNVx1ZDU1OFx1YjI5NCBcdWQ2OWZcdWMyMThcdWI5Y2NcdWQwN2MgXHViNGYxXHVjN2E1XHVkNTU4XHViMjk0IFx1YmU0NFx1YzViNFx1Yzc4OFx1YzljMCBcdWM1NGFcdWM3NDAgXHViZDgwXHViZDg0IFx1YjJlOFx1YzViNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIG0gKDAgJmxlOyBtICZsZTsgMSwwMDAsMDAwLDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YjJlOFx1YzViNCAmYWxwaGE7XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gJmFscGhhO1x1YjI5NCBhXHVjNjQwIGJcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVhZTM4XHVjNzc0XHViMjk0IDEsMDAwLDAwMFx1Yzc0NCBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViNDUwIFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjMjJiXHVjNzkwXHViMjk0IEZpYjxzdWI+bTxcL3N1Yj5cdWM1ZDAgJmFscGhhO1x1YWMwMCBcdWJkODBcdWJkODQgXHViMmU4XHVjNWI0XHViODVjIFx1Y2QxZCBcdWJhODcgXHViYzg4IFx1YjRmMVx1YzdhNVx1ZDU1OFx1YjI5NFx1YzljMFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjMjJiXHVjNzkwXHVjNzc0XHViMmU0LiBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YjJlOFx1YzViNFx1YjI5NCBGaWI8c3ViPm08XC9zdWI+XHVjNzU4IFx1YmFhOFx1YjRlMCBcdWJkODBcdWJkODQgXHViMmU4XHVjNWI0IFx1YzkxMVx1YzVkMFx1YzExYywgXHVjODAxXHVjNWI0XHViM2M0ICZhbHBoYTtcdWFjMDAgXHViNGYxXHVjN2E1XHVkNTU4XHViMjk0IFx1YjljY1x1ZDA3YyBcdWI0ZjFcdWM3YTVcdWQ1NThcdWIyOTQgXHViZTQ0XHVjNWI0XHVjNzg4XHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWJkODBcdWJkODQgXHViMmU4XHVjNWI0XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWMyMmJcdWM3OTBcdWIyOTQgXHViOWU0XHVjNmIwIFx1ZDA3NCBcdWMyMTggXHVjNzg4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCAyMDA2MjAwNlx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCAmYWxwaGE7XHViMjk0IFx1ZDU2ZFx1YzBjMSBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVkNTNjXHViY2Y0XHViMDk4XHVjZTU4IFx1YjJlOFx1YzViNFx1Yzc1OCBcdWJkODBcdWJkODQgXHViMmU4XHVjNWI0XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5GaWI8c3ViPjU8XC9zdWI+XHVjNWQwXHVjMTFjIFx1YzgwMVx1YzViNFx1YjNjNCBhYmFcdWFjMDAgXHViNGYxXHVjN2E1XHVkNTU4XHViMjk0IFx1YjljY1x1ZDA3YyBcdWI0ZjFcdWM3YTVcdWQ1NThcdWIyOTQgXHViZTQ0XHVjNWI0XHVjNzg4XHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWJkODBcdWJkODQgXHViMmU4XHVjNWI0XHViMjk0IGEsIGIsIGFiLCBiYSwgYWJhXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiODQwNiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkZpYm9uYWNjaSBXb3JkcyIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIHNlcXVlbmNlIG9mIEZpYm9uYWNjaSB3b3JkcyBpcyBkZWZpbmVkIGFzIGZvbGxvd3M6IEZpYjxzdWI+MDxcL3N1Yj4gPSBiLCBGaWI8c3ViPjE8XC9zdWI+ID0gYSwgRmliPHN1Yj5uPFwvc3ViPiA9IEZpYjxzdWI+bi0xPFwvc3ViPkZpYjxzdWI+bi0yPFwvc3ViPiBmb3IgbiAmZ2U7IDIuIEZpYjxzdWI+bjxcL3N1Yj4gaXMgdGhlIGNvbmNhdGVuYXRpb24gb2YgRmliPHN1Yj5uLTE8XC9zdWI+IGFuZCBGaWI8c3ViPm4tMjxcL3N1Yj4uPFwvcD5cclxuXHJcbjxwPlRoZSBmaXJzdCBmZXcgRmlib25hY2NpIHdvcmRzIGFyZTogYixhLGFiLGFiYSxhYmFhYixhYmFhYmFiYSxhYmFhYmFiYWFiYWFiLC4uLjxcL3A+XHJcblxyXG48cD5BIHdvcmQgdSBpcyBhIHN1YndvcmQgb2YgYSB3b3JkIHYgaWYgdiBjYW4gYmUgd3JpdHRlbiBhcyB2ID0geHV5IGZvciBzb21lIChwb3NzaWJseSBlbXB0eSkgd29yZHMgeCBhbmQgeS48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHdoaWNoOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPnJlYWQgYSB3b3JkICZhbHBoYTsgKGEgc2VxdWVuY2Ugb2YgbGV0dGVycyBhIGFuZCBiKSBhbmQgYSBzZXF1ZW5jZSBudW1iZXIgbSBvZiB0aGUgRmlib25hY2NpIHdvcmQgRmlibTs8XC9saT5cclxuXHQ8bGk+Y29tcHV0ZXMgdGhlIG51bWJlciBvZiB0aW1lcyB0aGUgd29yZCAmYWxwaGE7IG9jY3VycyBpbiBGaWJtIGFzIGEgc3Vid29yZCBhbmQgdGhlIG51bWJlciBvZiBub25lbXB0eSB3b3JkcyB0aGF0IG9jY3VyIGFzIGEgc3Vid29yZCBpbiBGaWI8c3ViPm08XC9zdWI+IGF0IGxlYXN0IGFzIGZyZXF1ZW50bHkgYXMgJmFscGhhOy48XC9saT5cclxuXHQ8bGk+d3JpdGVzIHRoZSBhbnN3ZXIgdG8gdGhlIHN0YW5kYXJkIG91dHB1dC48XC9saT5cclxuPFwvdWw+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgb25lIGludGVnZXIgbSAoMCAmbGU7IG0gJmxlOyAxIDAwMCAwMDAgMDAwKS4gV2Ugd2lsbCBleGFtaW5lIHRoZSBGaWJvbmFjY2kgd29yZCBGaWI8c3ViPm08XC9zdWI+LiBUaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgb25lIHdvcmQgJmFscGhhOyAoYSBzZXF1ZW5jZSBvZiBubyBtb3JlIHRoYW4gMSAwMDAgMDAwIGFuZCBubyBsZXNzIHRoYW4gb25lIGxldHRlciBhIGFuZFwvb3IgYikuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+SW4gdGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgeW91ciBwcm9ncmFtIHNob3VsZCB3cml0ZSB0d28gbnVtYmVycyBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2UuIFRoZSBmb3JtZXIgaXMgdGhlIG51bWJlciBvZiB0aW1lcyB0aGUgd29yZCAmYWxwaGE7IG9jY3VycyBpbiBGaWI8c3ViPm08XC9zdWI+IGFzIGEgc3Vid29yZC4gVGhlIGxhdHRlciBpcyB0aGUgbnVtYmVyIG9mIG5vbmVtcHR5IHdvcmRzIHdoaWNoIG9jY3VyIGluIEZpYm0gYXMgc3Vid29yZHMgYXQgbGVhc3QgYXMgZnJlcXVlbnRseSBhcyAmYWxwaGE7IG9jY3VycyBpbiBGaWI8c3ViPm08XC9zdWI+LjxcL3A+XHJcblxyXG48cD5Cb3RoIG51bWJlcnMgc2hvdWxkIGJlIHdyaXR0ZW4gbW9kdWxvIDIwMDYyMDA2ICh5b3Ugc2hvdWxkIHdyaXRlIHRoZSByZW1haW5kZXIgb2YgdGhlIGRpdmlzaW9uIG9mIHRoZXNlIG51bWJlcnMgYnkgMjAwNjIwMDYpLjxcL3A+XHJcblxyXG48cD5Zb3UgY2FuIGFzc3VtZSwgdGhhdCB0aGUgd29yZCAmYWxwaGE7IGlzIGEgc3Vid29yZCBvZiB0aGUgZ2l2ZW4gRmlib25hY2NpIHdvcmQuPFwvcD5cclxuIiwiaGludCI6IjxwPlRoZSBzdWJ3b3JkcyBvZiBGaWI8c3ViPjU8XC9zdWI+IHdoaWNoIG9jY3VyIGluIEZpYjxzdWI+NTxcL3N1Yj4gYXQgbGVhc3QgYXMgZnJlcXVlbnRseSBhcyBhYmEgYXJlOiBhLCBiLCBhYiwgYmEgYW5kIGFiYS48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Contest > Algorithmic Engagements > PA 2006 6-1번