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.
输入描述:
* 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.