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

문제

민식이는 애들과 토론 중이다. 안타깝게 민식이의 남의 말을 제대로 알아듣지 못한다. 민식이 귀가 다른 사람이 한 말을 인식하는 방법은 다음과 같다. 일단 민식이는 다른 사람이 말한 말을 2진수로 바꾸어 듣는다. 그리고 다른 사람이 한 말의 i번째 비트는 민식이가 인식하는 이진수의 j번째 비트에 위치하게 되는데 항상 |j - i| ≤ D가 성립한다. 이렇게 만들어진 이진수로 민식이는 알아듣게 된다.

만약 다른 사람이 한 말이 0110이라면 민식이가 알아듣는 이진수의 후보는 0101, 0110, 1001, 1010으로 총 4가지이다.

문제는 다른 사람이 말하는 이진수와 정수 D, K가 주어지면 민식이가 알아듣는 이진수 후보의 개수와 이 후보들 중 K번째로 작은 이진수를 출력하는 문제이다.

입력

첫 줄에는 이진수 비트의 개수 N(1 ≤ N ≤ 2,000)과 D(0 ≤ D < N), K(1 ≤ K ≤ 100,000,000)가 공백으로 구분되어 주어진다. 두 번째 줄에는 다른 사람이 말한 N비트의 2진수가 주어진다.

출력

첫 줄에 민식이가 알아들을 것으로 예상되는 2진수의 총 후보의 개수를 100,000,000로 나눈 나머지를 출력한다. 다음 줄에는 이 이진수의 후보 중 K번째로 작은 2진수를 출력한다.

예제 입력 1

4 1 3
0110

예제 출력 1

4
1001
W3sicHJvYmxlbV9pZCI6IjExNzEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYWNcdWM2MjRcdWM4MTUiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YmJmY1x1YzJkZFx1Yzc3NFx1YjI5NCBcdWM1NjBcdWI0ZTRcdWFjZmMgXHVkMWEwXHViODYwIFx1YzkxMVx1Yzc3NFx1YjJlNC4gXHVjNTQ4XHVkMGMwXHVhZTVkXHVhYzhjIFx1YmJmY1x1YzJkZFx1Yzc3NFx1Yzc1OCBcdWIwYThcdWM3NTggXHViOWQwXHVjNzQ0IFx1YzgxY1x1YjMwMFx1Yjg1YyBcdWM1NGNcdWM1NDRcdWI0ZTNcdWM5YzAgXHViYWJiXHVkNTVjXHViMmU0LiBcdWJiZmNcdWMyZGRcdWM3NzQgXHVhZGMwXHVhYzAwIFx1YjJlNFx1Yjk3OCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVkNTVjIFx1YjlkMFx1Yzc0NCBcdWM3NzhcdWMyZGRcdWQ1NThcdWIyOTQgXHViYzI5XHViYzk1XHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWIyZTQuIFx1Yzc3Y1x1YjJlOCBcdWJiZmNcdWMyZGRcdWM3NzRcdWIyOTQgXHViMmU0XHViOTc4IFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWI5ZDBcdWQ1NWMgXHViOWQwXHVjNzQ0IDJcdWM5YzRcdWMyMThcdWI4NWMgXHViYzE0XHVhZmI4XHVjNWI0IFx1YjRlM1x1YjI5NFx1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIFx1YjJlNFx1Yjk3OCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVkNTVjIFx1YjlkMFx1Yzc1OCBpXHViYzg4XHVjOWY4IFx1YmU0NFx1ZDJiOFx1YjI5NCBcdWJiZmNcdWMyZGRcdWM3NzRcdWFjMDAgXHVjNzc4XHVjMmRkXHVkNTU4XHViMjk0IFx1Yzc3NFx1YzljNFx1YzIxOFx1Yzc1OCBqXHViYzg4XHVjOWY4IFx1YmU0NFx1ZDJiOFx1YzVkMCBcdWM3MDRcdWNlNThcdWQ1NThcdWFjOGMgXHViNDE4XHViMjk0XHViMzcwIFx1ZDU2ZFx1YzBjMSB8aiAtIGl8ICZsZTsgRFx1YWMwMCBcdWMxMzFcdWI5YmRcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YjgwN1x1YWM4YyBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWM5YzQgXHVjNzc0XHVjOWM0XHVjMjE4XHViODVjIFx1YmJmY1x1YzJkZFx1Yzc3NFx1YjI5NCBcdWM1NGNcdWM1NDRcdWI0ZTNcdWFjOGMgXHViNDFjXHViMmU0LjxcL3A+XHJcbjxwPlx1YjljY1x1YzU3ZCBcdWIyZTRcdWI5NzggXHVjMGFjXHViNzhjXHVjNzc0IFx1ZDU1YyBcdWI5ZDBcdWM3NzQgMDExMFx1Yzc3NFx1Yjc3Y1x1YmE3NCBcdWJiZmNcdWMyZGRcdWM3NzRcdWFjMDAgXHVjNTRjXHVjNTQ0XHViNGUzXHViMjk0IFx1Yzc3NFx1YzljNFx1YzIxOFx1Yzc1OCBcdWQ2YzRcdWJjZjRcdWIyOTQgMDEwMSwgMDExMCwgMTAwMSwgMTAxMFx1YzczY1x1Yjg1YyBcdWNkMWQgNFx1YWMwMFx1YzljMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG48cD48aW1nIHdpZHRoPVwiMjIyXCIgaGVpZ2h0PVwiNzZcIiBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvMjAxMDAzXC9waWNwaWNwLkpQR1wiIFwvPjxcL3A+XHJcbjxwPlx1YmIzOFx1YzgxY1x1YjI5NCBcdWIyZTRcdWI5NzggXHVjMGFjXHViNzhjXHVjNzc0IFx1YjlkMFx1ZDU1OFx1YjI5NCBcdWM3NzRcdWM5YzRcdWMyMThcdWM2NDAgXHVjODE1XHVjMjE4IEQsIEtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTc0IFx1YmJmY1x1YzJkZFx1Yzc3NFx1YWMwMCBcdWM1NGNcdWM1NDRcdWI0ZTNcdWIyOTQgXHVjNzc0XHVjOWM0XHVjMjE4IFx1ZDZjNFx1YmNmNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWM2NDAgXHVjNzc0IFx1ZDZjNFx1YmNmNFx1YjRlNCBcdWM5MTEgS1x1YmM4OFx1YzlmOFx1Yjg1YyBcdWM3OTFcdWM3NDAgXHVjNzc0XHVjOWM0XHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NCBcdWJiMzhcdWM4MWNcdWM3NzRcdWIyZTQuPFwvcD4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNzc0XHVjOWM0XHVjMjE4IFx1YmU0NFx1ZDJiOFx1Yzc1OCBcdWFjMWNcdWMyMTggTigxICZsZTsgTiAmbGU7IDIsMDAwKVx1YWNmYyBEKDAgJmxlOyBEICZsdDsgTiksIEsoMSAmbGU7IEsgJmxlOyAxMDAsMDAwLDAwMClcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YjJlNFx1Yjk3OCBcdWMwYWNcdWI3OGNcdWM3NzQgXHViOWQwXHVkNTVjIE5cdWJlNDRcdWQyYjhcdWM3NTggMlx1YzljNFx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWJiZmNcdWMyZGRcdWM3NzRcdWFjMDAgXHVjNTRjXHVjNTQ0XHViNGU0XHVjNzQ0IFx1YWM4M1x1YzczY1x1Yjg1YyBcdWM2MDhcdWMwYzFcdWI0MThcdWIyOTQgMlx1YzljNFx1YzIxOFx1Yzc1OCBcdWNkMWQgXHVkNmM0XHViY2Y0XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyAxMDAsMDAwLDAwMFx1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM3NzQgXHVjNzc0XHVjOWM0XHVjMjE4XHVjNzU4IFx1ZDZjNFx1YmNmNCBcdWM5MTEgS1x1YmM4OFx1YzlmOFx1Yjg1YyBcdWM3OTFcdWM3NDAgMlx1YzljNFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMTcxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVHJhbnNtaXNzaW9uIERlbGF5IiwiZGVzY3JpcHRpb24iOiI8cD5GYXJtZXIgSm9obiBoYXMgdGFrZW4gdG8geW9kZWxpbmcgZnJvbSB0aGUgdG9wIG9mIHRoZSBiYXJuIGluIG9yZGVyIHRvIGNvbW11bmljYXRlIHdpdGggdGhlIGNvd3Mgb3V0IGluIHRoZSBwYXN0dXJlcy4gQmVpbmcgYm92aW5lIGFuZCBhbGwsIGNvd3MgY2FuIGhlYXIgYmluYXJ5IG1lc3NhZ2VzICgwJiMzOTtzIGFuZCAxJiMzOTtzKSBidXQgaGF2ZSB0cm91YmxlIHdpdGggcGVyZmVjdCBjb21tdW5pY2F0aW9ucyBiZWNhdXNlIEZKJiMzOTtzIHlvZGVsaW5nIGVjaG9lcyBvZmYgdGhlIHNpbG8uIEluIGZhY3QsIGluIGEgc2VxdWVuY2Ugb2YgTiAoMSAmbHQ7PSBOICZsdDs9IDIsMDAwKSBiaXRzLCBCZXNzaWUgd2lsbCBhbHdheXMgcmVjZWl2ZSBhIHNlcXVlbmNlIG9mIE4gYml0cywgd2l0aCB0aGUgc2FtZSBudW1iZXIgb2YgMHMgYW5kIDFzLCBidXQgZWFjaCAwIG9yIDEgbWlnaHQgYmUgZGVsYXllZC48XC9wPlxyXG5cclxuPHA+UHJlY2lzZWx5IHNwZWFraW5nLCBmb3IgYSBnaXZlbiBudW1iZXIgRCAoMCAmbHQ7PSBEICZsdDsgTiksIHRoZSBpLXRoIGJpdCBtaWdodCBiZSBoZWFyZCBhcyB0aGUgai10aCBvbmUgYXMgbG9uZyBhcyB8aSAtIGp8ICZsdDs9IEQgKGluIG90aGVyIHdvcmRzLCBubyBiaXQgYXBwZWFycyBpbiBhIHBvc2l0aW9uIGZhcnRoZXIgdGhhbiBkaXN0YW5jZSBEIGZyb20gaXRzIG9yaWdpbmFsIHBvc2l0aW9uKS48XC9wPlxyXG5cclxuPHA+Q29uc2lkZXIgdGhlIGZvbGxvd2luZyBtZXNzYWdlIGFzIGFuIGV4YW1wbGU6IDAxMTAuIEZvdXIgcG9zc2libGUgbWVzc2FnZXMgbWlnaHQgYmUgaGVhcmQgaWYgRCA9IDE6IDAxMDEsIDAxMTAsIDEwMDEsIGFuZCAxMDEwLjxcL3A+XHJcblxyXG48cD5HaXZlbiB0aGUgbWVzc2FnZSB0byBiZSB5b2RlbGVkIGJ5IEZKLCBhbG9uZyB3aXRoIHR3byBudW1iZXJzIEQgYW5kIEsgKDEgJmx0Oz0gSyAmbHQ7PSAxMDAsMDAwLDAwMCksIGRldGVybWluZSB0aGUgbnVtYmVyIG9mIGRpZmZlcmVudCBtZXNzYWdlcyB0aGF0IG1pZ2h0IGJlIGhlYXJkIGJ5IEJlc3NpZSwgbW9kdWxvIDEwMCwwMDAsMDAwLiBBbHNvIGRldGVybWluZSB0aGUgSy10aCBzbWFsbGVzdCBzdWNoIG1lc3NhZ2UgaW4gbGV4aWNvZ3JhcGhpY2FsIG9yZGVyIChpbiBiaW5hcnkgcmVwcmVzZW50YXRpb24sIHdpdGggMCBjb21pbmcgYmVmb3JlIDEpLiBJdCBpcyBndWFyYW50ZWVkIHRoYXQgSyB3aWxsIGJlIG5vIGxhcmdlciB0aGFuIHRoZSBudW1iZXIgb2YgZGlmZmVyZW50IHBvc3NpYmxlIG1lc3NhZ2VzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+KiBMaW5lIDE6IFRocmVlIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VyczogTiwgRCwgYW5kIEs8XC9wPlxyXG5cclxuPHA+KiBMaW5lIDI6IEZKJiMzOTtzIGJpbmFyeSBtZXNzYWdlLCBjb250YWluaW5nIGV4YWN0bHkgTiBiaXRzPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+KiBMaW5lIDE6IFRoZSBudW1iZXIgb2YgZGlmZmVyZW50IHBvc3NpYmxlIG1lc3NhZ2VzIHRoYXQgY2FuIGhlYXJkIGJ5IEJlc3NpZSwgbW9kIDEwMCwwMDAsMDAwPFwvcD5cclxuXHJcbjxwPiogTGluZSAyOiBUaGUgSy10aCBzbWFsbGVzdCBzdWNoIG1lc3NhZ2UgKGluIGJpbmFyeSByZXByZXNlbnRhdGlvbik8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=