Delayed Yodeling

Farmer John has taken to yodeling from the top of the barn to communicate with his cows. However, due to echoes off the silo, the binary message he sends (a sequence of 0's and 1's) may suffer a transmission delay. In a message of length \(N\) (where \(1 \le N \le 2000\)), every bit is received, and the total counts of 0's and 1's remain the same. The twist is that each bit originally at position \(i\) may appear in the received message at position \(j\) as long as \(|i - j| \le D\) (with \(0 \le D < N\)).

For example, consider the message 0110 with \(D = 1\). The possible received messages are:

• 0101
• 0110
• 1001
• 1010

Given the original message, the allowed delay \(D\), and an integer \(K\) (with \(1 \le K \le 10^8\)), your task is twofold:

1. Compute the total number of different messages that might be heard by Bessie, modulo \(100,000,000\).
2. Find the \(K\textsuperscript{th} smallest message in lexicographical order (with 0 considered smaller than 1).

Note: It is guaranteed that \(K\) is no larger than the total number of possible messages.

inputFormat

The input consists of two lines:

• The first line contains a binary string \(S\) of length \(N\) (\(1 \le N \le 2000\)).
• The second line contains two integers \(D\) and \(K\) separated by a space, where \(0 \le D < N\) and \(1 \le K \le 10^8\).

outputFormat

Output two lines:

• The first line contains the total number of different possible messages modulo \(100,000,000\).
• The second line contains the \(K\)th smallest message in lexicographical order.

sample

0110
1 1

4
0101