사오정

민식이는 남의 말을 제대로 알아듣지 못한다. 어떤 사람이 N자리 이진수를 말하면, 민식이는 그 소리를 조금 다르게 알아듣는다. 말한 이진수의 i번째 비트는 민식이가 알아듣는 이진수의 j번째 비트 자리로 가는데, 이때 항상 |j - i| ≤ D가 성립한다. 각 자리에는 원래 비트가 정확히 하나씩만 들어가므로, 민식이가 알아듣는 이진수는 말한 이진수의 각 비트를 원래 위치에서 최대 D칸까지 옮겨 만든 재배치(순열)이다.

예를 들어 말한 이진수가 0110이고 D = 1이면, 민식이가 알아들을 수 있는 이진수는 0101, 0110, 1001, 1010으로 모두 4가지이다.

말한 이진수와 정수 D, K가 주어질 때, 민식이가 알아들을 수 있는 서로 다른 이진수의 개수와, 그 후보들 중에서 K번째로 작은 이진수를 구하여라.

첫째 줄에 이진수의 자리 수 N (1 ≤ N ≤ 2,000), 정수 D (0 ≤ D < N), 정수 K (1 ≤ K ≤ 100,000,000)가 공백으로 구분되어 주어진다.

둘째 줄에 어떤 사람이 말한 N자리 이진수가 주어진다.

첫째 줄에 민식이가 알아들을 수 있는 서로 다른 이진수의 개수를 100,000,000으로 나눈 나머지를 출력한다.

둘째 줄에 그 후보들 중 K번째로 작은 이진수를 N자리 이진수로(맨 앞의 0도 그대로 포함하여) 출력한다.