题目描述

Farmer John has taken to yodeling from the top of the barn in order to communicate with the cows out in the pastures. Being bovine and all, cows can hear binary messages (0's and 1's) but have trouble with perfect communications because FJ's yodeling echoes off the silo. In fact, in a sequence of N (1 <= N <= 2,000) bits, Bessie will always receive a sequence of N bits, with the same number of 0s and 1s, but each 0 or 1 might be delayed.

Precisely speaking, for a given number D (0 <= D < N), the i-th bit might be heard as the j-th one as long as |i - j| <= D (in other words, no bit appears in a position farther than distance D from its original position). Consider the following message as an example: 0110. Four possible messages might be heard if D = 1: 0101, 0110, 1001, and 1010.

Given the message to be yodeled by FJ, along with two numbers D and K (1 <= K <= 100,000,000), determine the number of different messages that might be heard by Bessie, modulo 100,000,000. Also determine the K-th smallest such message in lexicographical order (in binary representation, with 0 coming before 1). It is guaranteed that K will be no larger than the number of different possible messages.

MEMORY LIMIT: 32 MB

TIME LIMIT: 2 seconds

FEEDBACK: Your first 50 submissions for this problem will be run on some of the official test data, and you will receive a summary of the results.

约翰在屋顶上唱歌，以此来与奶牛们交流。但是奶牛们的听力很奇怪，她们只能听到约翰的歌声变成 $0$ 和 $1$ 构成的信息串时的样子。约翰的声音里有 $N (1 \leq N \leq 2000)$ 个 $0$ 或 $1$，奶牛听到的也是 $N$ 个，而且 $0$ 和 $1$ 的数量不会变化，但是一部分 $0$ 或 $1$ 可能偏离原来的位置，这就是约翰的歌声在传输时发生的“传输延迟”现象。$0$ 或 $1$ 的偏离距离不会超过 $D(O \leq D < N)$，也就是说某一个码的原本位置和现在的位置之差的绝对值不大于 $D$。

比如，对于 0110，$D = 1$，传输延迟发生后可能出现 0101，0110，1001，1010 这四种串．

给出约翰歌声的 $01$ 串形式和一个整数 $K(1 \leq K \leq10^8)$，请计算传输延迟发生后一共有多少种可能的 $01$ 串，以及其中第 $K$ 大的串是什么。

输入格式

* Line 1: Three space-separated integers: N, D, and K

* Line 2: FJ's binary message, containing exactly N bits

输出格式

* Line 1: The number of different possible messages that can heard by Bessie, mod 100,000,000

* Line 2: The K-th smallest such message (in binary representation)

Note that if your program's first line of output is correct but the second line of output is either missing or wrong, you will receive 40% of the points for that test case.

4 1 3 
0110 

4 
1001