시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+bTxcL3N1Yj5cdWM3NDQgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IG1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHViNTRjLCBGaWI8c3ViPm08XC9zdWI+XHVjNWQwICZhbHBoYTtcdWFjMDAgXHViZDgwXHViZDg0IFx1YjJlOFx1YzViNFx1Yjg1YyBcdWJhODcgXHViYzg4IFx1YjRmMVx1YzdhNVx1ZDU1OFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWFjZTAsIEZpYjxzdWI+bTxcL3N1Yj5cdWM3NTggXHViZDgwXHViZDg0IFx1YjJlOFx1YzViNCBcdWM5MTFcdWM1ZDBcdWMxMWMmbmJzcDsmYWxwaGE7XHVhYzAwIFx1YzgwMVx1YzViNFx1YjNjNCBcdWI0ZjFcdWM3YTVcdWQ1NThcdWIyOTQgXHVkNjlmXHVjMjE4XHViOWNjXHVkMDdjIFx1YjRmMVx1YzdhNVx1ZDU1OFx1YjI5NCBcdWJlNDRcdWM1YjRcdWM3ODhcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YmQ4MFx1YmQ4NCBcdWIyZThcdWM1YjRcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBtICgwICZsZTsgbSAmbGU7IDEsMDAwLDAwMCwwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIyZThcdWM1YjQgJmFscGhhO1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICZhbHBoYTtcdWIyOTQgYVx1YzY0MCBiXHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YWUzOFx1Yzc3NFx1YjI5NCAxLDAwMCwwMDBcdWM3NDQgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjQ1MCBcdWMyMmJcdWM3OTBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1YjI5NCBGaWI8c3ViPm08XC9zdWI+XHVjNWQwICZhbHBoYTtcdWFjMDAgXHViZDgwXHViZDg0IFx1YjJlOFx1YzViNFx1Yjg1YyBcdWNkMWQgXHViYTg3IFx1YmM4OCBcdWI0ZjFcdWM3YTVcdWQ1NThcdWIyOTRcdWM5YzBcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzIyYlx1Yzc5MFx1Yzc3NFx1YjJlNC4gXHViNDUwIFx1YmM4OFx1YzlmOCBcdWIyZThcdWM1YjRcdWIyOTQgRmliPHN1Yj5tPFwvc3ViPlx1Yzc1OCBcdWJhYThcdWI0ZTAgXHViZDgwXHViZDg0IFx1YjJlOFx1YzViNCBcdWM5MTFcdWM1ZDBcdWMxMWMsIFx1YzgwMVx1YzViNFx1YjNjNCAmYWxwaGE7XHVhYzAwIFx1YjRmMVx1YzdhNVx1ZDU1OFx1YjI5NCBcdWI5Y2NcdWQwN2MgXHViNGYxXHVjN2E1XHVkNTU4XHViMjk0IFx1YmU0NFx1YzViNFx1Yzc4OFx1YzljMCBcdWM1NGFcdWM3NDAgXHViZDgwXHViZDg0IFx1YjJlOFx1YzViNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHVjMjJiXHVjNzkwXHViMjk0IFx1YjllNFx1YzZiMCBcdWQwNzQgXHVjMjE4IFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgMjAwNjIwMDZcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgJmFscGhhO1x1YjI5NCBcdWQ1NmRcdWMwYzEgXHVjOGZjXHVjNWI0XHVjOWM0IFx1ZDUzY1x1YmNmNFx1YjA5OFx1Y2U1OCBcdWIyZThcdWM1YjRcdWM3NTggXHViZDgwXHViZDg0IFx1YjJlOFx1YzViNFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+RmliPHN1Yj41PFwvc3ViPlx1YzVkMFx1YzExYyBcdWM4MDFcdWM1YjRcdWIzYzQgYWJhXHVhYzAwIFx1YjRmMVx1YzdhNVx1ZDU1OFx1YjI5NCBcdWI5Y2NcdWQwN2MgXHViNGYxXHVjN2E1XHVkNTU4XHViMjk0IFx1YmU0NFx1YzViNFx1Yzc4OFx1YzljMCBcdWM1NGFcdWM3NDAgXHViZDgwXHViZDg0IFx1YjJlOFx1YzViNFx1YjI5NCBhLCBiLCBhYiwgYmEsIGFiYVx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijg0MDYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJGaWJvbmFjY2kgV29yZHMiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBzZXF1ZW5jZSBvZiBGaWJvbmFjY2kgd29yZHMgaXMgZGVmaW5lZCBhcyBmb2xsb3dzOiBGaWI8c3ViPjA8XC9zdWI+ID0gYiwgRmliPHN1Yj4xPFwvc3ViPiA9IGEsIEZpYjxzdWI+bjxcL3N1Yj4gPSBGaWI8c3ViPm4tMTxcL3N1Yj5GaWI8c3ViPm4tMjxcL3N1Yj4gZm9yIG4gJmdlOyAyLiBGaWI8c3ViPm48XC9zdWI+IGlzIHRoZSBjb25jYXRlbmF0aW9uIG9mIEZpYjxzdWI+bi0xPFwvc3ViPiBhbmQgRmliPHN1Yj5uLTI8XC9zdWI+LjxcL3A+XHJcblxyXG48cD5UaGUgZmlyc3QgZmV3IEZpYm9uYWNjaSB3b3JkcyBhcmU6IGIsYSxhYixhYmEsYWJhYWIsYWJhYWJhYmEsYWJhYWJhYmFhYmFhYiwuLi48XC9wPlxyXG5cclxuPHA+QSB3b3JkIHUgaXMgYSBzdWJ3b3JkIG9mIGEgd29yZCB2IGlmIHYgY2FuIGJlIHdyaXR0ZW4gYXMgdiA9IHh1eSBmb3Igc29tZSAocG9zc2libHkgZW1wdHkpIHdvcmRzIHggYW5kIHkuPFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB3aGljaDo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5yZWFkIGEgd29yZCAmYWxwaGE7IChhIHNlcXVlbmNlIG9mIGxldHRlcnMgYSBhbmQgYikgYW5kIGEgc2VxdWVuY2UgbnVtYmVyIG0gb2YgdGhlIEZpYm9uYWNjaSB3b3JkIEZpYm07PFwvbGk+XHJcblx0PGxpPmNvbXB1dGVzIHRoZSBudW1iZXIgb2YgdGltZXMgdGhlIHdvcmQgJmFscGhhOyBvY2N1cnMgaW4gRmlibSBhcyBhIHN1YndvcmQgYW5kIHRoZSBudW1iZXIgb2Ygbm9uZW1wdHkgd29yZHMgdGhhdCBvY2N1ciBhcyBhIHN1YndvcmQgaW4gRmliPHN1Yj5tPFwvc3ViPiBhdCBsZWFzdCBhcyBmcmVxdWVudGx5IGFzICZhbHBoYTsuPFwvbGk+XHJcblx0PGxpPndyaXRlcyB0aGUgYW5zd2VyIHRvIHRoZSBzdGFuZGFyZCBvdXRwdXQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIG9uZSBpbnRlZ2VyIG0gKDAgJmxlOyBtICZsZTsgMSAwMDAgMDAwIDAwMCkuIFdlIHdpbGwgZXhhbWluZSB0aGUgRmlib25hY2NpIHdvcmQgRmliPHN1Yj5tPFwvc3ViPi4gVGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIG9uZSB3b3JkICZhbHBoYTsgKGEgc2VxdWVuY2Ugb2Ygbm8gbW9yZSB0aGFuIDEgMDAwIDAwMCBhbmQgbm8gbGVzcyB0aGFuIG9uZSBsZXR0ZXIgYSBhbmRcL29yIGIpLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkluIHRoZSBmaXJzdCBhbmQgb25seSBsaW5lIHlvdXIgcHJvZ3JhbSBzaG91bGQgd3JpdGUgdHdvIG51bWJlcnMgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlLiBUaGUgZm9ybWVyIGlzIHRoZSBudW1iZXIgb2YgdGltZXMgdGhlIHdvcmQgJmFscGhhOyBvY2N1cnMgaW4gRmliPHN1Yj5tPFwvc3ViPiBhcyBhIHN1YndvcmQuIFRoZSBsYXR0ZXIgaXMgdGhlIG51bWJlciBvZiBub25lbXB0eSB3b3JkcyB3aGljaCBvY2N1ciBpbiBGaWJtIGFzIHN1YndvcmRzIGF0IGxlYXN0IGFzIGZyZXF1ZW50bHkgYXMgJmFscGhhOyBvY2N1cnMgaW4gRmliPHN1Yj5tPFwvc3ViPi48XC9wPlxyXG5cclxuPHA+Qm90aCBudW1iZXJzIHNob3VsZCBiZSB3cml0dGVuIG1vZHVsbyAyMDA2MjAwNiAoeW91IHNob3VsZCB3cml0ZSB0aGUgcmVtYWluZGVyIG9mIHRoZSBkaXZpc2lvbiBvZiB0aGVzZSBudW1iZXJzIGJ5IDIwMDYyMDA2KS48XC9wPlxyXG5cclxuPHA+WW91IGNhbiBhc3N1bWUsIHRoYXQgdGhlIHdvcmQgJmFscGhhOyBpcyBhIHN1YndvcmQgb2YgdGhlIGdpdmVuIEZpYm9uYWNjaSB3b3JkLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5UaGUgc3Vid29yZHMgb2YgRmliPHN1Yj41PFwvc3ViPiB3aGljaCBvY2N1ciBpbiBGaWI8c3ViPjU8XC9zdWI+IGF0IGxlYXN0IGFzIGZyZXF1ZW50bHkgYXMgYWJhIGFyZTogYSwgYiwgYWIsIGJhIGFuZCBhYmEuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Contest > Algorithmic Engagements > PA 2006 6-1번