Misheard Binary

Minsik often mishears what other people say. When someone says an N-bit binary number, Minsik hears a slightly different number. The i-th bit of the spoken number ends up at the j-th position of the number Minsik hears, and it always holds that |j - i| ≤ D. Each position receives exactly one original bit, so the number Minsik hears is a rearrangement (permutation) of the spoken number in which every bit moves at most D places from its original position.

For example, if the spoken number is 0110 and D = 1, the numbers Minsik can hear are 0101, 0110, 1001, and 1010 — four in total.

Given the spoken binary number and the integers D and K, find how many distinct binary numbers Minsik can hear, and the K-th smallest among those candidates.

The first line contains the number of bits N (1 ≤ N ≤ 2,000), the integer D (0 ≤ D < N), and the integer K (1 ≤ K ≤ 100,000,000), separated by spaces.

The second line contains the spoken N-bit binary number.

On the first line, print the number of distinct binary numbers Minsik can hear, modulo 100,000,000.

On the second line, print the K-th smallest candidate as an N-bit binary number (keeping any leading zeros).