[Usaco2009 Hol]Transmission Delay 传输谍延时

时间限制:10s      空间限制:64MB

题目描述

    约翰在屋顶上唱歌,以此来与奶牛们交流.但是奶牛们的听力很奇怪,她们只能听到约翰的歌声变成0和1构成的信息串时的样子.    约翰的声音里有N(1≤N≤2000)个0或1,奶牛听到的也是N个,而且0和1的数量不会变化,但是一部分0或1可能偏离原来的位置,这就是约翰的歌声在传输时发生的“传输延迟”现象.0或1的偏离距离不会超过D(O≤D<N),也就是说某一个码的原本位置和现在的位置之差的绝对值不大于D.
    比如,对于0110,D=1,传输延迟发生后可能出现0101,0110,1001,1010这四种串.
    给出约翰歌声的01串形式和一个整数K(1≤K≤108),请计算传输延迟发生后一共有多少种可能的01串,以及其中第K大的串是什么.


输入格式

第一行输入 n , d , k 第二行输入那个N位的数字,用二进制表示


输出格式

分别输出受到整数的种数(将结果Mod 100,000,000),和这些整数第K小的那个


样例输入

4 1 3
0110

样例输出

4
1001

提示

1<=n<=2000 0<=k


题目来源

Gold