P2929 [USACO09HOL] Transmission Delay G

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

\* 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.