Description

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 testdata, and you will receive a summary of the results.

Farmer John sings from the rooftop to communicate with the cows. The cows can only hear the message when it is represented as a string of $0$ and $1$. There are $N (1 \leq N \leq 2000)$ bits in Farmer John's voice, and the cows will also hear $N$ bits, with the counts of $0$ and $1$ unchanged, but some bits may shift from their original positions due to “transmission delay.” The shift distance will not exceed $D(O \leq D < N)$, meaning the absolute difference between a bit’s original position and its received position is at most $D$.

For example, for 0110 with $D = 1$, the possible received strings are 0101, 0110, 1001, and 1010.

Given the $01$-string of Farmer John’s message and an integer $K(1 \leq K \leq10^8)$, compute the total number of possible $01$ strings after transmission delay, and find the K-th smallest string in lexicographical order.

Input Format

• Line 1: Three space-separated integers: N, D, and K.
• Line 2: FJ's binary message, containing exactly N bits.

Output Format

• Line 1: The number of different possible messages that can be heard by Bessie, modulo 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 

Hint

Translated by ChatGPT 5